首页 > 代码库 > √n求单值欧拉函数
√n求单值欧拉函数
基本定理:
首先看一下核心代码：
核心代码
原理解析：
当初我看不懂这段代码，主要有这么几个问题：
1.定理里面不是一开始写了一个n*xxx么？为什么代码里没有*n？
2.ans不是*(prime[i]-1)么？为什么到了第二个while循环变成*prime[i]了？
3.定理里面不是要/pi么？为什么代码里没有/pi?????????????
公式化简
首先我们来分析一下整个程序的原理，如果把程序的原理搞明白了，这三个问题也就自然而然的解决了
这个程序的原理是基于唯一分解定理：
那么我们可以把n拆开，再带回到欧拉函数公式中，然后再约分一下：
LaTex代码：
1 ans=p_1^a^1*p_2^a^2*.......*p_i^a^i*\frac{p_1-1}{p_1}*\frac{p_2-1}{p_2}*....*\frac{p_i-1}{p_i}2 \newline 3 =p_1^a^1*\frac{p_1-1}{p_1}*.......*p_2^a^2*\frac{p_2-1}{p_2}*....p_i^a^i*\frac{p_i-1}{p_i}4 \newline 5 =p_1^a^{1-1}*({p_1-1})*.......*p_2^a^{2-1}*({p_2-1})*....p_i^a^{i-1}*({p_i-1})
解答问题
首先这里的代码实现还有一个小技巧：
我们在while之前把x/prime[i]，这就相当于让ans少*一个prime[i]，这样就可以解决求指数ai-1的问题了
现在再回去看一下刚开始的三个问题，仔细想一想
提示：
下面有答案，
但请认真思考以后再看，
答案在下面：
1.定理里面不是一开始写了一个n*xxx么？为什么代码里没有*n？
因为n被唯一分解了，while循环里面的内容就是用来*n的
2.ans不是*(prime[i]-1)么？为什么到了第二个while循环变成*prime[i]了？
*prime是为了让答案最终*n
3.定理里面不是要/pi么？为什么代码里没有/pi?????????????
被化简了，不明白的可以看上面的化简过程
完整代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=1000001; 7 int prime[MAXN]; 8 int mu[MAXN]= {0,1}; 9 int n;10 int tot=0;11 int vis[MAXN]= {1,1};12 void read(int &n) {13 char c=‘+‘;14 int x=0;15 bool flag=0;16 while(c<‘0‘||c>‘9‘) {17 c=getchar();18 if(c==‘-‘)flag=1;19 }20 while(c>=‘0‘&&c<=‘9‘) {21 x=x*10+c-48;22 c=getchar();23 }24 flag==1?n=-x:n=x;25 }26 void ou() {27 for(int i=2; i<=n; i++) {28 if(!vis[i])29 prime[++tot]=i,mu[i]=-1;30 for(int j=1; j<=tot&&j*prime[i]<=n; j++) {31 vis[i*prime[j]]=1;32 if((i%prime[j])==0) {33 mu[i*prime[j]]=0;34 break;35 }36 mu[i*prime[j]]=-mu[i];37 }38 }39 }40 int getphi(int x) {41 int ans=1;42 for(int i=1; i<=tot&&prime[i]*prime[i]<=x; i++) 43 {44 if(x%prime[i]==0) 45 {46 ans*=(prime[i]-1);47 x=x/prime[i];48 while(x%prime[i]==0) 49 {50 ans*=prime[i];51 x/=prime[i];52 }53 }54 55 }56 if(x>1)57 ans*=x-1;58 return ans;59 }60 int main() {61 n=1001;62 ou();63 int c;64 printf("please input the num\n");65 while(cin>>c)66 printf("the num`s phi is %d\n",getphi(c));67 return 0;68 69 }
里面还乱入了线性求莫比乌斯函数的方法，，
懒得删了，，，
结尾啰嗦几句
求单值欧拉函数就讲到这里，
其实对于这份代码还有一种很玄学的理解方法，
但是我的这种方法比较简单易懂，
而且这两种理解方法从本质上来说是一样的
这里不在赘述
最后再说一下，这里只介绍了求单值欧拉函数的方法，
实际上欧拉函数还有线性筛法（因为欧拉函数是积性函数）
有空再介绍吧
另外，因为本人是第一次接触欧拉函数，所以本文肯定有成堆的bug，如果您找出了bug，可以在评论区留言或者通过其他方式联系本人，
谢谢！
√n求单值欧拉函数