P 315 GCDはXOR UVa 12176の「発見に難くない」解釈と完全な導出過程に等しい.

1. a-b<=a xor b,
同じ数値で同じバイナリビット値に対してxorと減算の効果は同じです.
同じ数桁で異なるバイナリビット値に対してxorは1に等しく、減算は高位に1を借りる可能性がある.
2.gcd(a,b)<=a-b(a>bと仮定)
gcd(a,b)=gcd(b,a%b)
a=qb+r=a%b=a-qbとする
gcd(b,a%b)=gcd(b,a-qb)
このとき最大公因数はa-qbを超えない
a-qb<=a-b
従ってgcd(a,b)=gcd(b,a%b)<=a-b
————————心が疲れた分割線——————明らかですか——————完全な構想の総括
c=a^b=gcd(a,b)がc=a-bを発見してこの結論が成立したことを証明するとする
c=a^b>=a-bの場合、同じ数位で同じバイナリビット値の場合、xorと減算の効果は同じです.同じ数桁で異なるバイナリビット値に対してxorは1に等しく、減算は高位に1を借りる可能性がある.
c=gcd(a,b)<=a-b(a>bと仮定)については、gcd(a,b)=gcd(b,a%b)をa=qb+r=a%b=a-qb gcd(b,a%b)=gcd(b,a-qb)とする場合、最大公因数はa-qbを超えず、a-qb<=a-bであるため、gcd(a,b)=gcd(b,a%b)<=a-bとなる
従って、上記条件を満たすc=a-b
gcdという層の関係があるaをcの倍数としてふるい分け、またc=a-bの関係を用いてa=ncとすると、gcd(a,b)=gcd(a,a-c)=gcd(nc,(n-1)c)=cとなる.nとn-1は互いに質的であるため、次にa^b=cを検証するだけでよい
少し気づいたかどうか分かりませんが、cnt++の位置はaです.デフォルトの大きな数です.a、bはいずれもn以下の条件を満たすべきですから、aの位置に記入してください.

/*SE:wn------  */
#include
using namespace std;
const int maxn = 30000000+1;
int cnt[maxn];
int sum[maxn]; 
int main()
{
	int i,j,n,runs,run,a,b,c;
	memset(cnt,0,sizeof(cnt)); memset(sum,0,sizeof(sum));
	/*  ：           
	        
	1.        2.           
	    ：  gcd(a,b)==a^b,  c=a-b
	3.         c=a-b   b
	    b=a-c         ？
	    gcd(a,b)=gcd(a,a-c)=c
	    b=a-c      gcd(a,b)==c    
	 c==a^b        
	  ：      ，b    a-c
	       ，gcd      */
	for(c=1;c<=15000000;c++)
		for(a=c*2;a<=30000000;a+=c)
		{
			b=a-c;
			if(c==(a^b)) ++cnt[a]; //1080ms
			/*b=a^c;
			if(b%c==0&&b