欧拉函数
定义
欧拉函数的定义为
Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n.
即不超过(n)的,与(n)互质的,正整数的个数。
所以根据定义,(phi(1)=1)。
计算公式
[varphi(n)=n prod_{p | n}left(1-frac{1}{p}
ight)
]
引理及其证明
[egin{array}{l}{ ext { If } p ext { is prime and } k geq 1 ext { , then }} \ {qquad varphileft(p^{k}
ight)=p^{k-1}(p-1)=p^{k}left(1-frac{1}{p}
ight)}end{array}
]
证明:
因为(p)为质数,所以(gcd(p^k,m))的取值为(1, p, p^{2}, ldots, p^{k})。而(gcd(p^k,m))不互质的唯一情况是(m)为(p)的倍数。
小于等于(p^k)的(p)的倍数有(p, 2 p, 3 p, ldots, p^{k-1} p=p^{k}),一共(p^{k-1})个。
所以小于等于(p^k)的,与(p^k)互质的数就有(p^k-p^{k-1})个。
计算公式的证明
(n=p_{1}^{k_{1}} cdots p_{r}^{k_{r}})
[egin{aligned} varphi(n) &=varphileft(p_{1}^{k_{1}}
ight) varphileft(p_{2}^{k_{2}}
ight) cdots varphileft(p_{r}^{k_{r}}
ight) \ &=p_{1}^{k_{1}}left(1-frac{1}{p_{1}}
ight) p_{2}^{k_{2}}left(1-frac{1}{p_{2}}
ight) cdots p_{r}^{k_{r}}left(1-frac{1}{p_{r}}
ight) \ &=p_{1}^{k_{1}} p_{2}^{k_{2}} cdots p_{r}^{k_{r}}left(1-frac{1}{p_{1}}
ight)left(1-frac{1}{p_{2}}
ight) cdotsleft(1-frac{1}{p_{r}}
ight) \ &=nleft(1-frac{1}{p_{1}}
ight)left(1-frac{1}{p_{2}}
ight) cdotsleft(1-frac{1}{p_{r}}
ight) end{aligned}
]
筛法
(sqrt n)筛
就是质因子分解之后根据计算公式计算答案。
inline int getphi(int x) {
int tmp = sqrt(x), res = x;
for (int i = 1; i <= tmp; i++) {
if (x % i == 0) {
res -= res / i;
while (x % i == 0) x /= i;
}
}
return x > 1 ? res - res / x : res;
}
埃氏筛
思路类似,如果一个(i)是合数就不管,如果是质数枚举其倍数,然后按照计算公式给这个数添加上这个质因子带来的贡献。
inline int getphi(int x){
for(int i=2;i<=x;i++){
if(phi[i])continue;//和数
for(int j=i;j<=x;j+=i){
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
return 0;
}
线性筛
线性筛的本质是每个数只会被它的最小质因子筛。
那么对于([2,n])中的每个数(i),我们都枚举它们的最小质因子(p)。那么就要保证(p)小于等于(i)的最小质因子,才能保证乘上(i imes p)的最小质因子为(p)。
对于(p)小于(i)的最小质因子的情况,则(i)没有包含质因子(p),那我们利用积性函数性质即可。
对于(p)等于(i)的最小质因子的情况,则(i)包含质因子(p),那我们根据欧拉函数计算公式可得(phi(i imes p)=phi(i) imes p)
void get_phi() {
phi[1]=1
for(int i=2;i<=n;i++) {
if(!pri[i])phi[i]=i-1,pri[++num]=i;
for(int j=1;j<=num&&i*pri[j]<=n;j++) {
pri[i*pri[j]]=1;
if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
else phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
}