[紫书CH10] 例题10-5：GCD等于XOR(数论、找规律、算法优化、UVa12716)

紫书题解汇总：[紫书CH0] 《算法竞赛入门经典》(第2版) 题解目录

1. 题目来源

链接：UVA12716 GCD XOR

2. 题目说明

中文描述：

3. 题目解析

方法一：数论+找规律+算法优化

例题10-5　GCD等于XOR（GCD XOR, ACM/ICPC Dhaka 2013, UVa12716）

按照书上的提示，记 $gcd(a,b)=a\oplus b =c$gcd(a,b)=a⊕b=c，那么根据异或的性质来讲，由 $a\oplus b =c$a⊕b=c 可得 $a \oplus c =b$a⊕c=b，那么就可以通过枚举 a 、c 计算得到 b 再验证是否满足 $gcd(a,b)=c$gcd(a,b)=c，就能够得到答案了。且由于 c 是 a 的约数，那么就相同于素数筛算法了，那这个时间复杂度就为 $\sum_{i=1}^n\frac{n}{i}=O(nlogn)$∑i=1n​in​=O(nlogn)。gcd 时间复杂度为 $O(logn)$O(logn)，则总的时间复杂度为 $O(n(logn)^2)$O(n(logn)2)。

这个算法仍存在优化点有上述算法打印一些结果满足 $gcd(a,b)=a\oplus b =c$gcd(a,b)=a⊕b=c 的三元组$(a,b,c)$(a,b,c)能够发现规律为 $c=a-b$c=a−b。关于这个规律的证明如下：不难发现 $a-b\leq a \oplus b 且 a-b \geq c$a−b≤a⊕b且a−b≥c 若存在 $c$c 使得 $a-b>c$a−b>c，则 $c <a-b \leq a \oplus b$c<a−b≤a⊕b，与 $c=a \oplus b$c=a⊕b 矛盾。

那么现在依旧枚举 $a、c$a、c，计算 $b=a-c$b=a−c，则 $gcd(a,b)=gcd(a,a-c)=c$gcd(a,b)=gcd(a,a−c)=c，因此仅验证 $c= a \oplus b$c=a⊕b 即可，时间复杂度降为 $O(nlogn)$O(nlogn)。

具体就是开辟两个 MAXN = 30000000; 一个 cnt 用来放置当前 index 为 a 时构成的满足要求的整数对。第一层循环遍历 c 第二层循环遍历 a 由于满足 c 一定是 a 的约数，所以 a 初始值可设为 2c 步长增量也为 c。若满足整数对条件，则 ++cnt[a]。循环完毕后，统计整数 n 的整数对数，即需要将前面的 cnt 累加起来即可。

参见代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
// 3e7 误写为3e8时本地竟然无法通过，不能正常打印,2e8可以，3e8报链接错误
const int MAXN = 30000000;
int cnt[MAXN + 50], sum[MAXN + 50];

void solve() {
	memset(cnt, 0, sizeof(cnt));
	for (int c = 1; c <= MAXN; ++c) {
		for (int a = c * 2; a <= MAXN; a += c) {
			int b = a - c;
			if (c == (a ^ b)) ++cnt[a];
		}
	}
	sum[0] = 0;
	for (int i = 1; i <= MAXN; ++i) sum[i] = sum[i - 1] + cnt[i];
}

int main() {
	solve();
	int T, n, tmp = 0;
	cin >> T;
	while (T--) {
		scanf("%d", &n);
		printf("Case %d: %d\n", ++tmp, sum[n]);
	}
	return 0;
}