最大公约数
给定整数 $N$，求 $1 leq x,y leq N$ 且 $text{GCD}(x,y)$ 为素数的数对 $(x,y)$ 有多少对。
$text{GCD}(x,y)$ 即求 $x$，$y$ 的最大公约数。
输入格式
输入一个整数 $N$。
输出格式
输出一个整数，表示满足条件的数对数量。
数据范围
$1 leq N leq {10}^{7}$
输入样例：
4
输出样例：
4
解题思路
直接枚举$(x, y)$是不可取的，如果定义一种映射关系$(x, y) stackrel{f}{longrightarrow} p$，其中$p$是质数。因此当数对$(x, y)$的最大公约数为质数就满足这个映射关系。可以发现自变量很多，而因变量很少，因此考虑能不能来枚举因变量来求自变量的个数。
枚举$1 sim N$种的每一个质数$p$，如果有$gcd(x, y) = p$，那么有$gcd(frac{x}{p}, frac{y}{p}) = 1$。记$x' = frac{x}{p}$，$y' = frac{y}{p}$，满足$1 leq x', y' leq leftlfloor {frac{N}{p}} rightrfloor$。因此问题从在$1 sim N$中有多少个$(x, y)$的$gcd(x, y) = p$变成了在$1 sim leftlfloor {frac{N}{p}} rightrfloor$中有多少个$(x, y)$的$gcd(x, y) = 1$，就是 可见的点的模型。
因此对于质数$p$，所要求的$(x, y)$的个数为$s_p = 2 cdot sumlimits_{i = 2}^{leftlfloor {frac{N}{p}} rightrfloor}{varphi(i)} + 1$。因此总的答案就是$sumlimits_{text{不超过N的质数}p}{s_p}$。因此还需要对$varphi(i)$求一个前缀和。
AC代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 1e7 + 10; 7 8 int primes[N], cnt; 9 bool vis[N]; 10 int phi[N]; 11 LL s[N]; 12 13 void get_prime(int n) { 14 // phi[1] = 1 // 这题中定义phi(1)=0 15 for (int i = 2; i <= n; i++) { 16 if (!vis[i]) primes[cnt++] = i, phi[i] = i - 1; 17 for (int j = 0; primes[j] <= n / i; j++) { 18 vis[primes[j] * i] = true; 19 if (i % primes[j] == 0) { 20 phi[primes[j] * i] = phi[i] * primes[j]; 21 break; 22 } 23 phi[primes[j] * i] = phi[i] * (primes[j] - 1); 24 } 25 } 26 } 27 28 int main() { 29 int n; 30 cin >> n; 31 get_prime(n); 32 for (int i = 1; i <= n; i++) { // 对phi[i]求前缀和 33 s[i] = s[i - 1] + phi[i]; 34 } 35 LL ret = 0; 36 for (int i = 0; i < cnt; i++) { 37 ret += 2 * s[n / primes[i]] + 1; 38 } 39 cout << ret; 40 41 return 0; 42 }
参考资料
AcWing 220. 最大公约数（算法提高课）：https://www.acwing.com/video/695/
原文链接: https://www.cnblogs.com/onlyblues/p/17063977.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/313483
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
