APP
1、AcWing基礎課：
線性篩：（與線性篩質(zhì)數(shù)對應）
phi[1] = 1; for (int i = 2; i <= n; i ++) { if (!st[i]) { primes[cnt ++] = i; phi[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++) { st[primes[j] * i] = true; if (i % primes[j] == 0) { phi[primes[j] * i] = phi[i] * primes[j]; break; } phi[primes[j] * i] = phi[i] * (primes[j] - 1); } }
證明：
?
?
2、參考：https://www.bilibili.com/video/BV1MK411f7RW?spm_id_from=333.337.search-card.all.click&vd_source=75ae018f8d1181302d7ea76b60c928f4
nloglogn篩：（貢獻度思想，與埃氏篩對應）
for (int i = 1; i <= n; i++) phi[i] = i; for (int i = 2; i <= n; i++) { if (phi[i] == i) { for (int j = i; j <= n; j += i) { phi[j] = phi[j] / i * (i - 1); } } }
?這里可以對應歐拉函數(shù)的求法：
“
歐拉函數(shù)的定義是，φ(n)是1-n中與n互質(zhì)的數(shù)的個數(shù)
對n分解質(zhì)因數(shù)得p1^a1*p2^a2*...*pn^an，
則φ(n)=n*(1-1/p1)(1-1/p2)*...*(1-1/pn);
”
初始化phi[i]=i，
如果沒有篩到，則確認為質(zhì)數(shù)，然后將此質(zhì)數(shù)p的倍數(shù)的phi，phi=phi/p*(p-1)
本文摘自 ：https://www.cnblogs.com/
