链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=594&problem=4669&mosmsg=Submission+received+with+ID+2196163

题意：给定n(1<=n<=3e7)，求有多少对整数(a,b)满足1<=b<=a<=n,gcd(a,b)=a^b。

分析：设gcd(a,b)=c，a^b=c等价于a^c=b，因此可以枚举a和c，然后检查gcd(a,a^c)==c，复杂度为O(n(longn)^2)，果断T。。实际上满足条件的数对必然满足b=a-c，因为b=a^c>=a-c，c=gcd(a,b)=gcd(a-b,b)<=a-b。因此只需要检验c==a^(a-c)。

复杂度为O(nlogn)，大约是7e8，但是有多组数据，因此要预处理前3e7个，记第i个为dp[i]，a=i时的数对有_a[i]对 ，则dp[i]=dp[i-1]+_a[i]，可以线性处理，总的复杂度为O(nlogn)。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int maxn=3e7+5; 7 bool have[maxn]; 8 long long _a[maxn],dp[maxn]; 9 long long ans=0;10 void solve(){11     ans=0;12     for(int c=1;c<=maxn;c++){13         for(int a=2*c;a<=maxn;a+=c){14             if((a^(a-c))==c)_a[a]++;15         }16     }17 }18 int main(){19     //freopen("e:\\in.txt","r",stdin);20     memset(_a,0,sizeof(_a));21     solve();22     dp[1]=0;23     for(int i=2;i
         
          >t;28     for(int kase=1;kase<=t;kase++){29         scanf("%d",&n);30         printf("Case %d: %d\n",kase,dp[n]);31     }32     return 0;33 }