UVA12716：GCD XOR

UVA12716：GCD XOR

题意:

给定(Tleq10^4)组测试样例，询问(sum_{i=1}^nsum_j^n[gcd(a,b)=a xor b])。

(nleq3*10^7)。

思路：

设

[gcd(a,b)=a xor b=c ]

• (1:a xor b=c)，那么有(a xor c=b).

• (2:a-bleq a xor b).

• (3:gcd(a,b)=a xor b=c)，令(a=k_1c,b=k_2c,(k_1geq k_2))。

  • (a-b=(k_1-k_2)*c)。
  • 又因为(a-bleq c)。
  • 所以有(a-b=c)。

所以结果为：

[a-b=a xor b ]

的数对对数。

时间复杂度

[n+frac{n}{2}+frac{n}{3}+...=n(1+frac{1}{2}+frac{1}{2}+...)=n(lnn+c) ]

(lnn+c)为调和级数求和。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e7+10;
int ans[maxn];

void init(int n)
{
    int k = n>>1;
    for(int b = 1; b <= k; b++)
    	for(int a = b+b; a <= n; a += b)
    	if((a^b) == a-b) ans[a]++;
    for(int i = 1; i <= n; i++)
        ans[i] += ans[i-1];
}

int cas;
inline void solve()
{
    int n; scanf("%d", &n);
    printf("Case %d: %d
", ++cas, ans[n]);
}

int main()
{
    init(maxn-5);
    int T; scanf("%d", &T);
    while(T--) solve();
    return 0;
}