算法竞赛进阶指南，190页，素数线性筛法，欧拉函数
本题要点： 1、线性筛法求素数的同时， 求出欧拉函数。其中使用了欧拉函数的两个性质： a） a, b 互质，那么 phi(a * b) = phi(a) * phi(b) b） p 是素数， p^2 能整除 n，那么phi(n) = phi(n / p) * phi( p) 2、 数组phi[i] 中存放的是 欧拉函数的前缀和，使用 long long 来存。 3、 对于某个数 k, phi[k]表示 小于等于k的数中，有多少个数对(x, y) 互质（x <= y）。 如果 k * p <= n, 说明最大公约数 gcd(x * p, y * p) = p。 也就是说，当 k <= n / p 时候，有 phi[k] * 2 个数对满足，其最大公约数是素数p。 4、 扫描每一个 n 以内的素数p，n以内的数对 (x, y) , gcd(x, y) == p 的数对一共有 phi[k] * 2 个。 全部累加起来。最后减去 pNum （n以内的素数总数）， 因为素数 和自己配对，调换顺序也是一样的。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MaxN = 10000010; long long phi[MaxN]; //这里存的是欧拉函数的前缀和 int prime[MaxN]; int pNum; int v[MaxN]; //v[i] 表示i的最小素数 long long n; void init_phi() //线性筛法求素数的同时， 求出欧拉函数 { phi[1] = 1; for(int i = 2; i <= n; ++i) { if(!v[i]) { v[i] = i; prime[++pNum] = i; phi[i] = i - 1; //素数的欧拉函数比其值小1 } for(int j = 1; j <= pNum; ++j) { if(prime[j] > v[i] || prime[j] > n / i) break; v[i * prime[j]] = prime[j]; phi[i * prime[j]] = phi[i] * (i % prime[j]? prime[j] - 1 : prime[j]); //欧拉函数的性质，a, b 互质，那么 phi(a * b) = phi(a) * phi(b) //p 是素数， p^2 能整除 n，那么phi(n) = phi(n / p) * phi(p) } phi[i] += phi[i - 1]; //这里算的是前缀和 } } void solve() { long long ans = 0; for(int i = 1; i <= pNum; ++i) { ans += phi[n / prime[i]]; } printf("%lld\n", 2 * ans - pNum); //减去 pNum 的原因是，素数 和自己配对，调换顺序也是一样的 } int main() { scanf("%lld", &n); init_phi(); solve(); return 0; } /* 4 */ /* 4 */