《洛谷深入浅出进阶篇》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互素的数字有多少个。
也就是求
。然后将*2 ，
由于可以取遍1~n/p，
别忘了r=1，t=1，的时候也算了两遍，所以
对于任意一个1~n的质数，其总方案就是：
最终的答案就是
所以我们只需要用筛法求欧拉函数，同时求它的前缀和，
#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;
}