欧拉函数线性筛

设p为质数，phi(n)为n的欧拉函数值。

phi( p)=p-1，显然从1到p-1都与p互质若i%p==0，则phi(i*p)=phi(i)*p

证明：首先知道两个条件，①用反证法很容易得出gcd(n,i)=1，则gcd(n+i,i)=1；②n,i不互质，则n+i,i不互质，gcd(n,i)=k(k>1)，n=ak，i=bk，n+i=(a+b)k。

[1,i]中与i不互质的数有i-phi(i)个， [i+1,i+i]中与i不互质的数也有i-phi(i)个，依次递推，得出[1,i*p]中与i不互质的数有p*(i-phi(i))个。

因为i%p==0，则若有k整除p，则必有k整除i，因此i*p的因数和i的因数是相同的。

故[1,i*p]中与i*p不互质的数为p*(i-phi(i))个，同时也为i*p-phi(i*p)，据此得出结论phi(i*p)=phi(i)*p。

若i%p!=0，则phi(i*p)=phi(i)*phi( p)，即phi(i*p)=phi(i)*(p-1)，积性函数的性质。

模板

int prime[maxn], phi[maxn], tot; bool vis[maxn]; void init() { phi[1] = 1; for (int i = 2; i < maxn; i++) { if (!vis[i]) { prime[++tot] = i; phi[i] = i - 1; } for (int j = 1; j <= tot && i * prime[j] < maxn; j++) { vis[i * prime[j]] = true; if (i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } }

应用

SP5971 LCMSUM - LCM Sum

#include<cstdio> using namespace std; typedef long long ll; const int maxn = 1e6 + 5; int prime[maxn], phi[maxn], tot; bool vis[maxn]; ll ans[maxn]; void solve() { phi[1] = 1; for (int i = 2; i < maxn; i++) { if (!vis[i]) { prime[++tot] = i; phi[i] = i - 1; } for (int j = 1; j <= tot && i * prime[j] < maxn; j++) { vis[i * prime[j]] = true; if (i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } for (int i = 1; i < maxn; i++) for (int j = 1; i * j < maxn; j++) ans[i * j] += 1LL * j * phi[j]; for (int i = 1; i < maxn; i++)ans[i] = (ans[i] + 1) * i / 2; } int main(void) { solve(); int t, n; scanf("%d", &t); while (t--){ scanf("%d", &n); printf("%lld\n", ans[n]); } return 0; }