[UVa12716]GCD XOR（数论）

题目链接：GCD XOR - UVA 12716 - Virtual Judge (vjudge.net)

最近在看紫书的时候看到这道题，但是感觉紫书上写的有点云里雾里，对于一些“不难发现”的不等式解释不够详细，这里做一下解释。

题目大意 / Problem

给定一个正整数N，问有多少对正整数（A，B）使得\(gcd(a, b) = a\oplus b\)，且有\(1 \le B \le A \le N\)。

分析 / Analyse

设\(c = a \oplus b\)，则有\(b = a \oplus c\)，同时又有\(c = gcd(a, b)\)，则我们可以枚举c和a（\(a = k * c\)），然后算出\(b = a \oplus c\)，再判断\(1\le B\le N \quad and \quad c=gcd(a, b)\)。这样时间复杂度是\(O(N(logN)^2)\)。N是3e7，非常恐怖，应该会超时。

所以我们继续优化，首先有\(a - b \le a \oplus b\)，这个的证明如下：

再证明\(a - b \ge gcd(a, b)\)。

所以有c<=a-b<=c，故c=a-b。

这样只需要枚举c和a = k*c，然后算出b = a - c，再判断b = a ^ c即可。

时间复杂度为\(O(NlogN)\)。

因为有多次询问，用前缀和即可。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e7 + 9;
int kase = 0;
int prefix[maxn];

void getprefix(int N)
{
	for(int c = 1;c <= N; ++ c)
	{
		for(int a = c;a <= N; a += c)
		{
			int b = a - c;
			if(1 <= b && b <= a && (a ^ b) == c)prefix[max(a, b)] ++;
		}
	}
	for(int i = 1;i <= N; ++ i)prefix[i] += prefix[i - 1];
}

void solve()
{
	int N;cin >> N;
	cout << "Case " << ++ kase << ": " << prefix[N] << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	getprefix(maxn - 5);
	int _;cin >> _;
	while(_ --)solve();
	
	return 0;
}