UVa 12716 - GCD XOR(筛选+规律)

输入一个数 n , ( 1 ≤ n ≤ 30000000 ) ,输出有多少对整数满足 1 ≤ a ≤ b ≤ n ,
g c d ( a , b ) = a ⨁ b 。
设 c = a ⨁ b ,则 a ⨁ c = b 。找规律可得,当满足条件时, c = a − b 。
因此,枚举 c 、 a ,对每一对验证 c = a ⨁ b 即可。时间复杂度 O ( n l o g n ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
using namespace std;
const int maxn=30000010;
int a[maxn];
void init(){
int k=maxn/2;
for(int i=1;i<k;++i)
for(int j=i+i;j<maxn;j+=i)
if(i==(j^(j-i))) ++a[j];
for(int i=1;i<maxn;++i)
a[i]+=a[i-1];
return;
}
int main(){
init();
int t,tt=0;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
printf("Case %d: %d\n",++tt,a[n]);
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。