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

思路：容易想到  形如  （2,3） （4,5）.....这种互质相邻且二进制位数相同的数一定满足要求。

那么对于gcd为2情况进行分析：

从gcd(a,b) = 2得到a/2,b/2互质，可以想到a/2与b/2相差只能是1，因为要使a^b = 2 a,b只有在第1位有差别，即差别为2，如果a/2与b/2相差超过1，那么a,b就不能相差2.

从gcd(a,b) = 3得到a/3.b/3互质，可以想到a/3与b/3相差只能是1，因为要使a^b = 3 a,b只有在第1位和第2位有差别，即差别为3，如果a/2与b/2相差超过1，那么a,b就不能相差3.

其他情况也是如此。

因此可以得到一个必要条件 即   a-b = gcd(a,b)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
const int maxn = 30000000+10;
typedef long long LL;
int N;
int ret[maxn];

void init() {
    for(int i = 3; i < maxn; i+=2) ret[i] = 1;
    for(int i = 2; i < maxn/2; i++) {
        for(int j = i+i; j < maxn; j += i) {
            int k = j-i;
            if( (k^j) == i){
                ret[j]++;
            }
        }
    }
    for(int i = 1; i < maxn; i++) ret[i] += ret[i-1];
}
int main(){
    int ncase,T=1;
    init();
    cin >> ncase;
    while(ncase--) {
        scanf("%d",&N);
        printf("Case %d: %d\n",T++,ret[N]);
    }
    return 0;
}

UVa 12716 GCD XOR （简单证明）