UVa 12716 - GCD XOR（筛选＋规律）

发表于 分类于 ， Disqus：

输入一个数 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博客，格式可能有所偏差。 **