2的欧拉函数值为什么是

一.欧拉函数

1.算法描述

1u223cN 中与 N 互质的数的个数被称为欧拉函数，也就是说，1~N中与N的最大公约数是1的数的个数，记作phi left ( N ight )。

在算术基本定理中，若

N=p_{1}^{alpha _{1}}p_{2}^{alpha _{2 }}cdot cdot cdot p_{n}^{alpha _{n}}

则：

phi left ( N ight )=Nleft ( 1-frac{1}{p_{1}} ight )left ( 1-frac{1}{p_{2}} ight )cdot cdot cdot left ( 1-frac{1}{p_{n}} ight )

证明如下：我们可以分以下几步求出N的互质的数

1.在1~N这些数中，将p1、p2、……pn的倍数剔除，很显然，pi的倍数和N的最大公约数是不是1.

N-frac{N}{p_{1}}-frac{N}{p_{2}}-cdot cdot cdot -frac{N}{p_{n}}

2.但需要注意是，在1~N这些数中，pi*pj的倍数倍剔除了两次，因此要把他们加上

frac{N}{p_{1}p_{2}}+frac{N}{p_{1}p_{3}}+cdot cdot cdot +frac{N}{p_{n-1}p_{n}}

3.但是，对于pi*pj*pk的倍数，在第1步时，被剔除了三次，在第2步时，被pi*pj、pi*pk、pj*pk加上了三次，因而我们需要把pi*pj*pk的倍数再剔除一次：

-frac{N}{p_{1}p_{2}p_{3}}-frac{N}{p_{1}p_{2}p_{4}}-cdot cdot cdot -frac{N}{p_{n-2}p_{n-1}p_{n}}

4.那么可以想到，接下来就是所有N除以四项乘积的和，减去N除以五项乘积的和……

事实上，将所有的这些式子加起来，得到的就是

phi left ( N ight )=Nleft ( 1-frac{1}{p_{1}} ight )left ( 1-frac{1}{p_{2}} ight )cdot cdot cdot left ( 1-frac{1}{p_{n}} ight )

首先，当分母为奇数个乘积时，那每一项的符号都是-1的奇数次方，还是-1；当分母为偶数个乘积时，每一项的符号都是-1的偶数次方，为正。

这个公式可以类比于约数的个数,道理是一样的。

left ( p_{1}^{0}+p_{1}^{1} +cdot cdot cdot + p_{1}^{alpha _{1}} ight )left ( p_{2}^{0}+p_{2}^{1} +cdot cdot cdot + p_{2}^{alpha _{2}} ight )cdot cdot cdot left ( p_{n}^{0}+p_{n}^{1} +cdot cdot cdot + p_{n}^{alpha _{n}} ight )

2.代码实现

可以发现，欧拉函数并不关心每个质因子的指数是什么，因而我们不用s来存储指数，也不用map来存储质因子，每当我们发现一个质数i时，让结果乘以(1-1/i)。但需要注意两点：

1.对于(1-1/i)，1/i是小数，就这么写的话，那每一项都是1了，所以要×i再÷i，即：res=res/i*(i-1)。

2.一定要记得在循环结束后，判断x是否会大于1，如果大于1，说明还存在x这个质因子，再执行一步：res=res/x*(x-1)。

具体代码：

#include<iostream>
using namespace std;
int n;
int main(){
cin>>n;
while(n--){
int x;
cin>>x;
int res=x;
for(int i=2;i<=x/i;i++){
if(x%i==0){
while(x%i==0){
x=x/i;//i是我的一个质数
}
res=res/i*(i-1);
}
}
if(x>1) res=res/x*(x-1);//注意
cout<<res<<endl;
}
}
二.筛法求欧拉函数

1.算法描述

第一部分中的算法适合于求单个给定数字对应的欧拉函数的值，但是当题目要求求1~N所有数字的欧拉值之和时，用第一部分中的算法就会花费很多时间，下介绍用筛法求欧拉函数：

首先我们回顾筛法求质数的过程，对于给定的正整数N：

for(int i=2;i<=n;i++){
if(!str[i]){
primes[cnt++]=i;
}
else{
for(int j=0;primes[j]<=n/i;j++){
str[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
通过筛法，所有的质数，合数我们都可以遍历到，把所有的质数加入数组primes中，并且str[i*primes[j]]保证了每一个数都会被它的最小质因子筛掉，而if(i%primes[j]==0)保证了不会被重复标记，详细介绍可以参考：

https://blog.csdn.net/qq_64637770/article/details/127200421?spm=1001.2014.3001.5501

那如何做出修改让筛法求欧拉函数？

1.首先，对于质数i，那么1~i-1都与i互质，那么phi left (i ight )=i-1

2.对于合数，即我用str[i*primes[j]]将一个合数筛掉时，我必须同时把它的欧拉值求出来，我们分为以下两种情况：

A.若i可以整除primes[j]，那么primes[j]*i和i有共同的质因子，这是因为primes[j]是i的质因子，那么phi left ( i ight )已经包括了1-frac{1}{primes[j]}这一项，而欧拉函数的值与指数无关，因而：

phi left ( i*primes[j] ight )=primes[j]*phi left ( i ight )

B.若i不能够整除primes[j]，那么primes[j]*i比i多一个质因子primes[j]，这是因为i本身不包含质因子primes[j]，而primes[j]本身是质数，不会再有质因子，因而：

phi left ( i*primes[j] ight )=primes[j]left ( 1-frac{1}{primes[j]} ight )phi left ( i ight )=left ( primes[j] -1 ight )phi left ( i ight )

因而，每一个数的欧拉值都可以通过该种方法求出来。

2.代码实现

关于代码实现需要注意的是，res的值可能会很大，所以要定义成long long类型。

具体代码：

#include<iostream>
using namespace std;
int x;
const int N=1000010;
long long res;//最后的欧拉函数的值的和，有可能会非常大，要用long long
bool str[N];//是否被标记过
int primes[N];//存放质因子
int cnt;
int phi[N];//各个N的函数值
int main(){
phi[1]=1;//1的欧拉值为1捏
cin>>x;
for(int i=2;i<=x;i++){
if(!str[i]){//如果没有被标记过，那么是质数
phi[i]=i-1;//质数的欧拉值就是i-1
primes[cnt++]=i;
}
for(int j=0;primes[j]<=x/i;j++){
str[i*primes[j]]=true;//首先我一定能把所有的合数遍历到，这是肯定的
if(i%primes[j]==0){
//如果i可以整除primes[j]的话,那么i和primes[j]*i的最小质因子是相同的
phi[i*primes[j]]=primes[j]*phi[i];
break;
}
else{
//如果i不可整除primes[j]的话，那么i和primes[j]*i就相差一个primes[j]这个最小质因子
phi[i*primes[j]]=primes[j]*phi[i]*(primes[j]-1)/primes[j];
//那这样就把所有数的欧拉值都存在phi中
}
}
}
for(int i=1;i<=x;i++){
res=res+phi[i];
}
cout<<res;
}

一.欧拉函数1.算法描述1u223cN 中与 N 互质的数的个数被称为欧拉函数，也就是说，1~N中与N的最大公约数是1的数的个数，记作phi left ( N ight )。在算术基本定理中，若N=p_{1}^{alpha _{1}}p_{2}^{alpha _{2 }}cdot cdot cdot p_{n}^{alpha _{n}}则：phi left ( N ight )=Nleft ( 1-frac{1}{p_{1}} ight )left ( 1-frac{1}{p_{2}} ight )cdot cdot cdot left ( 1-frac{1}{p_{n}} ight )证明如下：我们可以分以下几步求出N的互质的数1.在1~N这些数中，将p1、p2、……pn的倍数剔除，很显然，pi的倍数和N的最大公约数是不是1.N-frac{N}{p_{1}}-frac{N}{p_{2}}-cdot cdot cdot -frac{N}{p_{n}}2.但需要注意是，在1~N这些数中，pi*pj的倍数倍剔除了两次，因此要把他们加上frac{N}{p_{1}p_{2}}+frac{N}{p_{1}p_{3}}+cdot cdot cdot +frac{N}{p_{n-1}p_{n}}3.但是，对于pi*pj*pk的倍数，在第1步时，被剔除了三次，在第2步时，被pi*pj、pi*pk、pj*pk加上了三次，因而我们需要把pi*pj*pk的倍数再剔除一次：-frac{N}{p_{1}p_{2}p_{3}}-frac{N}{p_{1}p_{2}p_{4}}-cdot cdot cdot -frac{N}{p_{n-2}p_{n-1}p_{n}}4.那么可以想到，接下来就是所有N除以四项乘积的和，减去N除以五项乘积的和……事实上，将所有的这些式子加起来，得到的就是phi left ( N ight )=Nleft ( 1-frac{1}{p_{1}} ight )left ( 1-frac{1}{p_{2}} ight )cdot cdot cdot left ( 1-frac{1}{p_{n}} ight )首先，当分母为奇数个乘积时，那每一项的符号都是-1的奇数次方，还是-1；当分母为偶数个乘积时，每一项的符号都是-1的偶数次方，为正。这个公式可以类比于约数的个数,道理是一样的。left ( p_{1}^{0}+p_{1}^{1} +cdot cdot cdot + p_{1}^{alpha _{1}} ight )left ( p_{2}^{0}+p_{2}^{1} +cdot cdot cdot + p_{2}^{alpha _{2}} ight )cdot cdot cdot left ( p_{n}^{0}+p_{n}^{1} +cdot cdot cdot + p_{n}^{alpha _{n}} ight )2.代码实现可以发现，欧拉函数并不关心每个质因子的指数是什么，因而我们不用s来存储指数，也不用map来存储质因子，每当我们发现一个质数i时，让结果乘以(1-1/i)。但需要注意两点：1.对于(1-1/i)，1/i是小数，就这么写的话，那每一项都是1了，所以要×i再÷i，即：res=res/i*(i-1)。2.一定要记得在循环结束后，判断x是否会大于1，如果大于1，说明还存在x这个质因子，再执行一步：res=res/x*(x-1)。具体代码：#include<iostream>using namespace std;int n;int main(){cin>>n;while(n--){int x;cin>>x;int res=x;for(int i=2;i<=x/i;i++){if(x%i==0){while(x%i==0){x=x/i;//i是我的一个质数}res=res/i*(i-1);}}if(x>1) res=res/x*(x-1);//注意cout<<res<<endl;}}二.筛法求欧拉函数1.算法描述第一部分中的算法适合于求单个给定数字对应的欧拉函数的值，但是当题目要求求1~N所有数字的欧拉值之和时，用第一部分中的算法就会花费很多时间，下介绍用筛法求欧拉函数：首先我们回顾筛法求质数的过程，对于给定的正整数N：for(int i=2;i<=n;i++){if(!str[i]){primes[cnt++]=i;}else{for(int j=0;primes[j]<=n/i;j++){str[i*primes[j]]=true;if(i%primes[j]==0) break;}}}通过筛法，所有的质数，合数我们都可以遍历到，把所有的质数加入数组primes中，并且str[i*primes[j]]保证了每一个数都会被它的最小质因子筛掉，而if(i%primes[j]==0)保证了不会被重复标记，详细介绍可以参考：https://blog.csdn.net/qq_64637770/article/details/127200421?spm=1001.2014.3001.5501那如何做出修改让筛法求欧拉函数？1.首先，对于质数i，那么1~i-1都与i互质，那么phi left (i ight )=i-12.对于合数，即我用str[i*primes[j]]将一个合数筛掉时，我必须同时把它的欧拉值求出来，我们分为以下两种情况：A.若i可以整除primes[j]，那么primes[j]*i和i有共同的质因子，这是因为primes[j]是i的质因子，那么phi left ( i ight )已经包括了1-frac{1}{primes[j]}这一项，而欧拉函数的值与指数无关，因而：phi left ( i*primes[j] ight )=primes[j]*phi left ( i ight )B.若i不能够整除primes[j]，那么primes[j]*i比i多一个质因子primes[j]，这是因为i本身不包含质因子primes[j]，而primes[j]本身是质数，不会再有质因子，因而：phi left ( i*primes[j] ight )=primes[j]left ( 1-frac{1}{primes[j]} ight )phi left ( i ight )=left ( primes[j] -1 ight )phi left ( i ight )因而，每一个数的欧拉值都可以通过该种方法求出来。2.代码实现关于代码实现需要注意的是，res的值可能会很大，所以要定义成long long类型。具体代码：#include<iostream>using namespace std;int x;const int N=1000010;long long res;//最后的欧拉函数的值的和，有可能会非常大，要用long longbool str[N];//是否被标记过int primes[N];//存放质因子int cnt;int phi[N];//各个N的函数值int main(){phi[1]=1;//1的欧拉值为1捏cin>>x;for(int i=2;i<=x;i++){if(!str[i]){//如果没有被标记过，那么是质数phi[i]=i-1;//质数的欧拉值就是i-1primes[cnt++]=i;}for(int j=0;primes[j]<=x/i;j++){str[i*primes[j]]=true;//首先我一定能把所有的合数遍历到，这是肯定的if(i%primes[j]==0){//如果i可以整除primes[j]的话,那么i和primes[j]*i的最小质因子是相同的phi[i*primes[j]]=primes[j]*phi[i];break;}else{//如果i不可整除primes[j]的话，那么i和primes[j]*i就相差一个primes[j]这个最小质因子phi[i*primes[j]]=primes[j]*phi[i]*(primes[j]-1)/primes[j];//那这样就把所有数的欧拉值都存在phi中}}}for(int i=1;i<=x;i++){res=res+phi[i];}cout<<res;}