欧拉函数
欧拉函数:定义\(\varphi (n)\)表示不超过\(n\)的与\(n\)互质的正整数个数
特别的：\(\varphi (1)=1\)
给出一些例子：
\(\varphi (2)=1,\varphi (3)=2,\varphi (4)=2,\varphi (5)=4\)
不难得出若\(n\)为质数，则\(\varphi (n)=n-1\)
欧拉函数的常用性质
-
1.若\(p\)是质数，则\(\varphi(p^n)=p^{n-1}(p-1)\)
这个结论很显然，首先有\(p^{n}\)个正整数不超过\(p^n\)，且每\(p\)个正整数有一个与其不互质
则每\(p\)个正整数有\(p-1\)个与其互质
所以\(\varphi(p^n)=p^n\times \frac{p-1}{p}=p^{n-1}(p-1)\) -
2.若\(a|x\),则\(\varphi(ax)=a\times \varphi(x)\)
考虑分组，先考虑\(1到x\)内的情况
对于一个数\(k\),它如果与\(x\)互质，因为\(a|x\)，则\(k\)与\(a\)也互质
从而可以得到：\(k\)与\(ax\)互质。
所以\(1到x\)满足条件的数就是\(\varphi(x)\)
显然的，对于这样的\(k\),\(k+x\)显然也与\(ax\)互质
那么每一组都有\(\varphi(x)\)个数了
有没有可能更多呢，答案是否定的。
考虑一个\(k\)使得与\(ax\)不互质而\(k-x\)与\(ax\)互质
显然是不可能的
又因为总共有\(a\)组，故\(\varphi(ax)=a\times \varphi(x)\) -
3.若a,b互质，则\(\varphi(a)\times \varphi(b)=\varphi(ab)\)
欧拉函数积性函数
欧拉函数的求法：
- 1.方法1，用定义发求单个\(x\)的欧拉函数\(\varphi(x)\)
\(\varphi(x)=x\times \frac{p_1-1}{p_1} \times .... \times \frac{p_k-1}{p_k}\)
int phi(int xx){
int a=xx,xi=xx;
for(int i=2;i<=sqrt(xx);i++){
if(xi%i==0){
a/=i;
a*=(i-1);
}
while(xi%i==0) xi/=i;
}
if(xi!=1){
a/=xi;
a*=(xi-1);
}
return a;
}
- 2.方法2，线性筛求欧拉函数
void init(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(vis[i]==0){
primes.push_back(i),phi[i]=i-1;
}
for(int j=0;j<primes.size();j++){
int p=primes[j];
if(p*i>n) break;
vis[p*i]=1;
if(i%p==0){
phi[p*i]=phi[i]*p;
}
else{
phi[p*i]=phi[p]*phi[i];
}
}
}
return;
}