鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > c++ > >

√n求单值欧拉函数

来源:互联网 作者:佚名 时间:2017-09-20 09:33
基本定理: 首先看一下核心代码: 核心代码 原理解析: 当初我看不懂这段代码,主要有这么几个问题: 1.定理里面不是一开始写了一个n*xxx么?为什么代码里没有*n? 2.ans不是*(prime[i]-1)么?为什么到了第二个while循环变成*prime[i]了? 3.定理里面不是要/p

基本定理:

 

 

首先看一下核心代码:

核心代码

 

 

原理解析:

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

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,可以在评论区留言或者通过其他方式联系本人

 

谢谢!

网友评论
<