前言
本人能力有限，有错误欢迎指出。
定义
\(\varphi(n)\) 表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。
公式
设 \(n=\prod\limits_{i=1}^{s}p_i^{k_i}\)，有
\[\begin{aligned}\varphi(n)&=\prod_{i=1}^s\varphi(p_i^{k_i})\\&=\prod_{i=1}^sp_i^{k_i}-p_i^{k_i-1}\\&=\prod_{i=1}^sp_i^{k_i}(1-p_i^{-1})\\&=\prod_{i=1}^sp_i^{k_i}(1-\frac{1}{p_i})\\&=\prod_{i=1}^sp_i^{k_i}\prod_{i=1}^s(1-\frac{1}{p_i})\\&=n\prod_{i=1}^s(1-\frac{1}{p_i})\end{aligned} \]性质
- 欧拉函数是积性函数。具体地：
- 当 \(gcd(n,m)=1\) 时，\(\varphi(n \times m)=\varphi(n) \times \varphi(m)\)。
- 否则，\(\varphi(n \times m)=\varphi(n) \times m\)。
- \(n=\sum_{d|n}{\varphi(d)}\)，即 \(n\) 的因数（包括 \(1\) 和 \(n\)）的欧拉函数之和等于 \(n\)。
代码
- 求单个 \(\varphi(n)\)。
long long eular(long long n) {
long long ans=n;
for(int i=2;i*i<=n;i++) {
if(n%i==0) {
ans−=ans/i;
while(n%i==0)
n/=i;
}
}
if(n>1)ans−=ans/n;
return ans;
}
- 求多个 \(\varphi(n)\)，利用欧拉筛和性质 \(1\)。
void init(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!is[i]){
pri[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*pri[j]<=n;j++){
is[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]];
}
}
}
}