【题目来源】
洛谷：P2568 GCD - 洛谷
【题目描述】
给定正整数 \(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\) 为素数的数对 \((x,y)\) 有多少对。
【输入】
只有一行一个整数，代表 \(n\)。
【输出】
一行一个整数表示答案。
【输入样例】
4
【输出样例】
4
【解题思路】
【算法标签】
《洛谷 P2568 GCD》 #素数判断,质数,筛法# #前缀和# #欧拉函数#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10000005;int n, f[N], sa[N], ans; // f: 欧拉函数值, sa: 欧拉函数前缀和, ans: 最终答案
int B[N]; // 标记数组，B[i]=1表示i是合数
vector<int> ve; // 存储质数// 线性筛法计算欧拉函数
void euler()
{f[1] = 1; // φ(1)=1for (int i = 2; i <= n; i++){ if (!B[i]) // 如果i是质数{ve.push_back(i); // 加入质数表f[i] = i - 1; // 质数的欧拉函数值为i-1}// 用当前已找到的质数筛去合数for (int j = 0; j < ve.size() && i * ve[j] <= n; j++){B[i * ve[j]] = 1; // 标记i*ve[j]为合数if (i % ve[j] == 0) // 如果ve[j]是i的最小质因子{// 当i*ve[j]有平方因子时，φ(i*ve[j]) = φ(i) * ve[j]f[i * ve[j]] = f[i] * ve[j]; break; // 关键：确保每个合数只被最小质因子筛一次}else // 如果ve[j]与i互质{// 当i与ve[j]互质时，φ(i*ve[j]) = φ(i) * φ(ve[j])f[i * ve[j]] = f[i] * f[ve[j]];}}}
}signed main()
{cin >> n; // 输入neuler(); // 线性筛计算1~n的欧拉函数值// 计算欧拉函数前缀和for (int i = 1; i <= n; i++){sa[i] = sa[i - 1] + f[i];}// 计算最终答案for (int i = 0; i < ve.size(); i++) // 遍历所有质数{ans += 2 * sa[n / ve[i]] - 1; // 计算贡献}cout << ans << endl; // 输出结果return 0;
}
【运行结果】
4
4