[UVa12716]GCD XOR(数论)

发布于 2022-09-29  314 次阅读


题目链接: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<=a^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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-09-29