UVA12716 GCD等于XOR GCD XOR 题解

题目链接：UVA12716 GCD等于XOR GCD XOR

题意：

求

$$\sum_{1 \le a \le n}\sum_{1 \le b \le a} \left[\gcd(a,b) = a \oplus b\right]$$

其中 $1 \le n \le 3\times 10^7$

令 $c = \gcd(a,b)$ ，则 $a - b \le a \oplus b = c$

令 $a = k_1c,~ b = k_2c~(k_1 > k_2)$ 则 $a - b = (k_1 - k_2) c \Rightarrow a - b \ge c$

则 $a - b = c = a\oplus b$ 。这样枚举 $a,c$ 就可以啦~

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
const int N = 3e7 + 5;

int ans[N + 15];
void init()
{
    int k = N / 2;
    for(int c = 1; c <= k; c++)
        for(int a = c + c; a <= N; a += c)
            if((a ^ (a - c)) == c) ++ans[a];
    for(int i = 2; i <= N; i++) ans[i] += ans[i - 1];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init(); int Q; scanf("%d", &Q);
    for(int i = 1, x; i <= Q; i++)
    {
        scanf("%d", &x);
        printf("Case %d: %d\n",i,ans[x]);
    }
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/cmwqf/gcd-xor