设gcd(a, b) = a xor b = c
那么我们可以证明ｃ＝ａ－ｂ
那么同时ｃ又是ａ的因子（ｃ是ａ与ｂ的最大公因数）
所以我们可以枚举ｃ，然后枚举ｃ的倍数，也就是ａ
有了ａ和ｃ可以算出ｂ为ａ－ｃ
然后最后验算是否a xor b = c就ｏｋ了。
这里的枚举方式非常的巧妙，是反过来枚举ｃ
来推ａ，如果枚举ａ的因子ｃ的话就会很耗时间了。
#include<cstdio>
#include<cmath>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 30000001;
int cnt[MAXN], sum[MAXN];void init()
{REP(c, 1, MAXN)for(int a = c * 2; a < MAXN; a += c)if(c == (a ^ (a - c))) cnt[a]++;REP(i, 1, MAXN) sum[i] = sum[i-1] + cnt[i];
}int main()
{init();int T, kase = 0, n;scanf("%d", &T);while(T--){scanf("%d", &n);printf("Case %d: %d\n", ++kase, sum[n]);}return 0;
}