题目：Given an integer N, and how many pairs (A;B) are there such that: gcd(A;B) = A xor B where 1<=B<=A<=N.
首先先爆一发，妥妥超时。其实真相是我想打表找规律。结果没什么规律可循。
后来分析：要想让GCD(A,B)==(A^B)，A和B一定是同样的位数（二进制）。因此打表方法可变为：（亦超时）
void init() { int K=0; int last=0; for(int i=1;i<=MAX;i++) { if(!(i&(1<<K))) last+=(1<<K),K++; //j应该在i到 1111..11范围内 for(int j=i+1;j<=(last+(1<<K));j++) if((i^j)==gcd(i,j)) ans[j]++; } for(int i=1;i<=MAX;i++) ans[i]+=ans[i-1]; }显然打表范围仍然很大。 后来看到网上清一色的使用 （i^(i-j)）==j来做的（j是i的因子），神啊，居然想到用j作为因数来枚举，但这个式子仍苦思不得其解。要用这个式子做，就要证明一个问题：为什么 i 和 i+k*j ,(k>=2)是不同位数的。和同学讨论后得出如下证明：
设最大公约数为 j, 假设这两个数是b 和 b+k*j，（k>=2）,设b的二进制数位数为C1，b+k*j的位数为C2，j的位数一定小于或等于C1,为C3。则k*j的位数一定大于或等于C3+1，（试想k=2时，k*j相比j左移了一位）。
若C1<C2,显然 b^(b+k*j)>b>=j,不满足。
若C1=C2，则b和b+k*j的最高不同位一定是b该位0，而b+k*j的那位为1。（最高不同位：10000和11000，最高不同位在左数第2位）。又由于b+k*j-b=k*j，因此这个最高不同位的位数一定大于j 的位数。因此 （b+k*j）^b>j，不满足。
若C1>C2.则（不可能有这个情况、、除非j为负数）。
综上所述，我们只需要枚举 b 和 b+1*j 是不是满足条件即可。
总结：能想到用j作为因数来枚举已经很神了，而在j的循环里面能想到只枚举 i 与 i-j就更神了。正解如下：
void init() { for(int i=1;i<MAX;i++) for(int j=i+i;j<MAX;j+=i) if((j^(j-i))==i) ans[j]++; //ans[j]只统计了与j相关的且满足条件的总对数 for(int i=1;i<=MAX;i++) ans[i]+=ans[i-1]; }
转载于:https://www.cnblogs.com/Airplus/p/3923494.html
相关资源：JAVA上百实例源码以及开源项目