首页 > 代码库 > U4704 函数

U4704 函数

2024-08-13 20:22:20   217人阅读

 

U4704 函数

    • 0通过
    • 105提交
  • 题目提供者飞翔
  • 标签
  • 难度尚无评定

  

最新讨论

  • 暂时没有讨论

题目背景

设gcd(a,b)为a和b的最大公约数，xor(a,b)为a异或b的结果。

最大公约数

异或

题目描述

kkk总是把gcd写成xor。今天数学考试恰好出到了gcd(a,b)=?这样的题目，但是kkk全部理解成了xor(a,b)=?

幸好这是填空题，老师只看kkk的答案是否正确而不在意过程。于是kkk想知道，对于所有不超过N的正整数a和b（a>=b）有多少组(a,b)满足可以使kkk的答案是正确的？

输入输出格式

输入格式：

 

一个整数N

 

输出格式：

 

输出(a,b)的组数

 

输入输出样例

输入样例#1：
7
输出样例#1：
4

说明

1<=N<=100000

题意：

问整数n以内，有多少对整数a、b满足(1≤b≤a)且gcd(a, b) = xor(a, b)

分析：

gcd和xor看起来风马牛不相及的运算，居然有一个比较"神奇"的结论：

设gcd(a, b) = xor(a, b) = c， 则 c = a - b

这里

有比较严格的证明。

有了这个结论后，我们可以枚举约数c，然后枚举c的倍数a，再根据c = a - b计算b，检验b是否满足gcd(a, b) = xor(a, b)

90代码（最后一个点不知道是什么坑）：

#include<cstdio>using namespace std;int n,ans;int main(){    scanf("%d",&n);    for(int c=1;c<=n;c++){        for(int a=c*2;a<=n;a+=c){            int b=a-c;            if((a^c)==b) ans++;        }    }    printf("%d\n",ans);    return 0;}

 

U4704 函数


联系
我们