欧拉函数
定义
对于任意的正整数 \(n\)，欧拉函数 \(\phi(n)\) 表示小于等于 \(n\) 的所有数中与 \(n\) 互质的数的个数。
暴力实现
那么根据定义，不难直接打出一个时间复杂度 \(O(n)\) 的代码，枚举所有小等于 \(n\) 的数字 \(i\)，若 \(\gcd(n,i)=1\) 则答案 \(+1\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int gcd(int x,int y)
{
return !y?x:gcd(y,x%y);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
if(gcd(i,n)==1)
ans++;
printf("%d\n",ans);
return 0;
}
很显然，这段代码效率不够高。有没有什么可以优化的地方？
欧拉函数推导
先根据定义可知以下几点：
- \(\phi(1)=1\)
- 若 \(n\) 为质数，则 \(\phi(n)=n-1\)，即除了 \(n\) 自己外全都算。
- 若 \(n=p^k\)，则 \(\phi(n)=p^k-p^{k-1}\)。因为只有一个数不含质数 \(p\)，才可以与 \(n\) 互质。所以就要剪掉包含质数 \(p\) 的那 \(p^{k-1}\) 个数字。而 \(p^k-p^{k-1}=p^k(1-\frac{1}{p})=p^k\frac{p-1}{p}\)。
- 若 \(n=ab\)，其中 \(a,b\) 互质，则 \(\phi(n)=\phi(a)\times\phi(b)=(a-1)\times(b-1)\)。反过来也一样，\(\phi(ab)=\phi(a)\times\phi(b)\)。
- 若 \(n=p_1^{k_1}p_2^{k_2}\cdots p_i^{k_i}\cdots p_m^{k_m}\)，则根据第三点，可表示为 \(p_1^{k_1}\frac{p_1-1}{p_1}p_2^{k_2}\frac{p_2-1}{p_2}\cdots p_m^{k_m}\frac{p_m-1}{p_m}\)。
再把 \(p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}\) 拎出来，发现正好等于 \(n\)，所以结果就变成了：
\[\phi(n)=n(\frac{p_1-1}{p_1})(\frac{p_2-1}{p_2})\cdots (\frac{p_m-1}{p_m}) \]根据这个公式，我们就可以枚举 \(p_i\) 去求解 \(\phi(n)\)。代码：
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main(){
scanf("%d",&n);
ans=n;
if(n==1)//特判
{
printf("1\n");
return 0;
}
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
ans=ans*(i-1)/i;//公式
while(!(n%i))//能整除就一直除下去
n/=i;
}
}
if(n>1)//如果n还没有除尽
ans=ans*(n-1)/n;
printf("%d\n",ans);
return 0;
}