【题解】UVa 12716【GCD XOR】

背景

分析

显然$a\ xor\ b = c$有$a\ xor\ c=b$,枚举$a$和$c$,然后算出$b$,最后验证$gcd$。

代码

#include<cstdio>

const int MAXN = 30000000 + 6;
int cnt[MAXN];

void init(){
    for(int c = 1;c <= (MAXN >> 1);c++){
        for(int a = c * 2;a <= MAXN;a += c){
            int b = a - c;
            if(c == (a ^ b)) cnt[a]++;
        }
    }
    for(int i = 2;i <= MAXN;i++) cnt[i] += cnt[i - 1];
}

int main(){
    init();
    int t,id = 1;scanf("%d",&t);
    while(t--){
        int n;scanf("%d",&n);
        printf("Case %d: %d\n",id++,cnt[n]);
    }
    return 0;
}