欧拉函数
定义
\(\{1\sim N\}\)中与\(N\)互质的数的个数被称作欧拉函数，即\(\varphi(N)\)
对于质数\(N\)，有\(\varphi(N)=N-1\)
性质
-
欧拉函数是积性函数
对于\(\gcd(a,b)=1\)，\(\varphi(a\times b)=\varphi(a)\times \varphi(b)\)
-
对于\(n>1\),\(1\sim n\)中满足\(\gcd(i,n)=1\)的数的和为\(n\times \frac {\varphi(n)} 2\)
-
\(n=\sum_{d|n} \varphi(d)\)
-
在唯一分解定理\(n={p_1}^{c_1}{p_2}^{c_2}...{p_n}^{c_n}\)
(\(\{p_1,p_2,...,p_n\}\)均为质数)中，则\[\varphi(n)=n\times\frac{p_1-1}{p_1}\times \frac {p_2-1}{p_2}...\times \frac {p_m-1}{p_m} \]\[\varphi(n)=n\times\prod_{i=1}^{n}(1-\frac 1 {p_i}) \]\[\varphi(n)=n\times\prod_{i=1}^{n}\frac {p_i-1} {p_i} \] -
对于 \(n=p^k\) , 且 \(p\) 是质数,则 \(\varphi(n)=p^k-p^{k-1}\)
-
\(n=\sum_{d|n}\varphi(d)\)
实现
求单独一个数
求单独一个数\(n\)的欧拉函数\(\varphi(n)\)
inline int phi(int n){
int ret=n;
for(int i=2;i*i<=(n);i++)
if(!(n%i)){
ret=ret/i*(i-1);
while(!(n%i)) n/=i;
}
if(n>1) ret=ret/n*(n-1);
return ret;
}
筛法求欧拉函数
每一个合数都是被最小的质因子筛掉。比如设 \(p_1\) 是 \(n\) 的最小质因子，
\(n' = \frac{n}{p_1}\) ，那么线性筛的过程中 \(n\) 通过 \(n' \times p_1\) 筛掉。
对 \(n'\bmod p_1\) 分情况讨论
若 \(n'\bmod p_1 = 0\) ，则 \(n'\) 包含了 \(n\) 的所有质因子
\[\begin{aligned} \varphi(n) & = n \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\\\ & = p_1 \times n' \times \prod_{i = 1}^s{\frac{p_i - 1}{p_i}} \\\\ & = p_1 \times \varphi(n') \end{aligned}
\]
若 \(n' \bmod p_1 \neq 0\) ，则 \(n'\) 和 \(p_1\) 是互质的
\[\begin{aligned} \varphi(n) & = \varphi(p_1) \times \varphi(n') \\\\ & = (p_1 - 1) \times \varphi(n') \end{aligned}
\]
std::vector<int> pri;
bool f[N];
int phi[N];
inline void pre(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!f[i]){
pri.push_back(i);
phi[i]=i-1;
}
for(int j:pri){//遍历数组
if(i*j>n) break;
f[i*j]=1;
if(i%j==0){
phi[i*j]=phi[i]*j;
break;
}
phi[i*j]=phi[i]*phi[j];
}
}
}