《洛谷深入浅出进阶篇》p2568 GCD-拓冰建站

P2568 GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P2568

大致题意：给定正整数n，求1<= x,y<=n 且 gcd（x，y）为素数的数对（x，y）有多少对。（n<=10^7)

思路：不如找n以内的所有的素数，然后统计每一个素数，是哪些数的最大公约数。

假设gcd（x，y）=p，设x=tp，y=rp；则 t与r必然互质。

由于x，y<=n，那么 t，r<=n/p。

所以，假设r更大，那么我们只要求1~r中与r互素的数字有多少个。

也就是求 $\psi\left(k \right )$ 。然后将 $\psi\left(k \right )$ *2 ，

由于可以取遍1~n/p，

别忘了r=1，t=1，的时候也算了两遍，所以

对于任意一个1~n的质数，其总方案就是： $2*\sum_{i=1}^{n/p}\psi\left(i \right )-1$

最终的答案就是 $\sum_{t=1}^{tot}(2*\sum_{i=1}^{n/p_{t}}(\psi\left(i \right ))-1$

所以我们只需要用筛法求欧拉函数，同时求它的前缀和，

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>using namespace std;
const int N = 1e7 + 7;
int pri[N], phi[N], flag[N];  // 质数表， 欧拉函数 ， 标记函数
long long sumphi[N];  // 前缀和数组
int tot;// 有多少个质数
int main() {int n;cin >> n;phi[1] = sumphi[1] = 1;  //预处理 1 的情况for (int i = 2; i <= n; i++) {if (flag[i] == 0) {   //套线性筛的板子pri[tot++] = i;phi[i] = i - 1;   }sumphi[i] = sumphi[i - 1] + phi[i];    //处理前缀和for (int j = 0; j < tot and pri[j] * i <= n; j++) {  flag[i * pri[j]] = 1;if (i % pri[j] == 0) {phi[i * pri[j]] = pri[j] * phi[i];break;}else {phi[i * pri[j]] = (pri[j] - 1) * phi[i];}}}long long ans = 0;for (int i = 0; i < tot; i++) {ans += sumphi[n / pri[i]] * 2 - 1;}cout << ans;
}