GCD 与XOR

题目：UVA12716

题意：  问 gcd(i,j) = i ^ j  的对数（j <=i <= N ） N的范围为30000000，有10000组样例

分析：

　有几个结论：（1）若 a xor b = c，则 a xor c = b。

　　　　　　　　（2）a - b <= a xor b，（a >= b)

　　　　　　　　（3）若 gcd（a，b）= a xor b = c ，（a >= b），由（2）得：a - b <= c。

　　　　　　　　　　  再令 a = k1×c，b = k2 × c，（k1 >= k2)，所以 a - b = （k1 - k2）× c，所以 a - b >= c。总：a - b = c

　　　　　　　　　　 （这里若k1 = k2，那么 a = b，那么 a xor b = 0）

　　然后就是怎么枚举的问题了，要保证计算量尽量小，如果枚举a，就要枚举a的所有因数，有些数因为可能是多个数的因数，会被重复考虑很多次。所以这里要枚举因数 c ，a = k × c（k >= 2) 这样每个因数只枚举一遍，再检验b。

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxm=3e7+5;
int s[maxm];
void init()
{
    for(int c=1;c<maxm/2;c++)
    {
        for(int a=c+c;a<maxm;a+=c)
        {
            int b=a-c;
            if((a^b)==c)
                s[a]++;
        }
    }
    for(int i=2;i<maxm;i++)
        s[i]+=s[i-1];
}
int main()
{
    int t;
    scanf("%d",&t);
    int k=0;
    init();
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("Case %d: %d
",++k,s[n]);
    }
}