首页 > > 程序设计 > C/C++ >

√n求单值欧拉函数

2018-06-17 22:11:08来源：未知阅读 ()

基本定理:

首先看一下核心代码：

核心代码

原理解析：

当初我看不懂这段代码，主要有这么几个问题：

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 }