12716 - GCD XOR

这道题的关键是怎样在nlogn的时间内找到a的约数（也叫因子）。因为a的范围很大，每次都搜索一遍肯定不行，我试过一次，连第二个样例都出不来。

所以要事先打好答案表。到时候直接查找就行了。然后就像紫书上说的一样，用公式b=a-c求出c；

就像筛法求素数一样，我们可以模仿这个方法筛出约数。怎么筛呢，答案就是枚举c，a必然是c的倍数。

#include<bits/stdc++.h>
using namespace std;
const int ans = 30000000;
int vis[ans];
int T,n;
void init() {
    memset(vis,0,sizeof(vis));
    for(int c=1;c<ans/2;++c)
    for(int a=c+c;a<=ans;a+=c){
        if(c==(a^(a-c))) vis[a]++;
    }
    for(int i=2;i<=ans;i++) vis[i]+=vis[i-1];//递推出每一项的答案数。
}
int main() {
    init();
    int maxn = 0;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        printf("Case %d: %d\n",++maxn,vis[n]);
    }
    return 0;
}

12716 - GCD XOR

原文：http://blog.csdn.net/weizhuwyzc000/article/details/44537401