欧拉函数

本人不懒,只是觉得写不出这么好的文章来,所以转大佬们的博客已传播之。代码部分有修改,各位可以看原文章
转自:https://www.cnblogs.com/handsomecui/p/4755455.html
算法总结
一欧拉函数(Euler's totient function)

欧拉函数的定义:
在数论中,对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数,记作φ(n)。
φ函数的值:
φ(x)=x(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(n)) 其中p(1),p(2)…p(n)为x
的所有质因数; x是正整数; φ(1)=1(唯一和1互质的数,且小于等于1)。注意:每种质因数只有一个。
例如:
φ(10)=10×(1-1/2)×(1-1/5)=4;
1 3 7 9
φ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;
φ(49)=49×(1-1/7)=42;

欧拉函数的性质:
(1)p^k型欧拉函数:
若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。
若N是质数p的k次幂(即N=p^k),φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。
(2)mn型欧拉函数
设n为正整数,以φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值。若m,n互质,φ(mn)=(m-1)(n-1)=φ(m)φ(n)。
(3)特殊性质:
若n为奇数时,φ(2n)=φ(n)。
对于任何两个互质 的正整数a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 欧拉定理
当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1)=1 mod n (恒等于)此公式即 费马小定理

欧拉函数的延伸:
于或等于n的数中,与n互质的数的总和为:φ(x) * x / 2(n>1)。

欧拉函数相关的证明:
(1)p^k型的欧拉函数的证明:
对于给定的一个素数p: φ(p)=p-1 那么容易证明φ(n)=p^k-p^(k-1)
已知少于或等于p^k的正整数的个数为p^k-1,其中和p^k不互质的正整数有{ p×1,p×2,...,p×(p^(k-1)-1)},共计p^(k-1)-1个
故: φ(n) = p^k-1-(p^(k-1)-1)=p^k-p^(k-1)。
(2)mn型的欧拉函数的证明:
因为:x=mn m与n互质(即:gcd(m,n)=1); 根据中国剩余定理Z(x)和Z(m)×Z(n)之间存在一一映射,所以x的完全余数集(见下面参考)中的元素的个数Z(x)等于Z(m)×Z(n)元素的个数;而Z(m)×Z(n)= φ(m)φ(n)
故有: φ(mn) =φ(m)φ(n) 成立。
(3)任意正整数的欧拉函数的相关证明:
任意一个整数n都可以表示为其质因子的乘积:
n=(p(1)*k(1)) *(p(2)*k(2)) *(p(3)*k(3))…(p(i)*k(i))*…*(p(I)*k(I)) 其中I为n 的质因子的个数。
根据(1)(2)的结论,很容易得出它的欧拉函数为:
φ(n)=n(1-1/p(1))(1-1/p(2))(1-1/p(3))(1-1/p(4))…..(1-1/p(i)) 其中I为n 的质因子的个数。
【欧拉函数】对于任意n>2,2|φ(n) 必定存在 p(i)-1是偶数

欧拉定理的相关证明:
(1)令Z(n)={ X(1),X(2),…,X(φ(n)) }S={ a*X(1) mod n, a*X(2) mod n ,…,a*X(φ(n)) mod n },则 Z(n)=S。
1)因为a与n互质(即:gcd(a,n)=1), X(i)(1≤i≤φ(n))与n互质(即:gcd(X(i),n)=1); 所以
a*X(i)与n互质(即:gcd(a*X(i),n)=1),故 a*X(i) mod n ∈ Z(n)。
2)若i≠j,那么 X(i)≠X(j) ,又有a与n互质(即:gcd(a,n)==1),则可得出: a*(X(i)) mod n ≠a*X(j) mod n (消去定律)。
(2)a^(φ(n))*X(1)*X(2)*X(3)*…*X(φ(n)) mod n
=(a*X(1))*(a*X(2))*(a*X(3))*…*(a*X(φ(n))) mod n
=(a*X(1) mod n)*(a*X(2) mod n)*(a*X(3) mod n)*…*(a*X(φ(n)) mod n) mod n
=X(1)*X(2)*X(3)*…*X(φ(n)) mod n。
对比等式左右两端,因为X(i)(1≤i≤φ(n))与n互质(即:gcd(X(i),n)==1) ,
故: a^φ(n)=1 mod n (恒等于)成立。

费马小定理的相关证明:
若正整数 a与素数p互质,则有a^(p-1)=1 mod n(恒等于)
由于φ(p)=p-1 且 a^φ(n)=1 mod n ,又有此处的p==n;
故:a^(p-1)=1 mod n成立。
此定理可以用来简化幂的模运算:
例如: 计算 7^222的个位数,实际上是求7^222被10除的余数。
且7与10互质,φ(10)=1,由欧拉定理知7^4= 1mod 10
故7^222=(7^4)^55*(7^2)=>(1^55)*(7^2)=>49=>9 mod 10

相关知识参考:

完全余数集合:
定义小于 n 且和 n 互质的数构成的集合为 Z(n) ,称呼这个集合为 n 的完全余数集合。 显然 |Z(n)| =φ(n) 。

同余定理:
如果 a mod b = c 则有(a+kb) mod b =c(k为非0整数)
如果 a mod b = c 则有(ka) mod b =kc (k为正整数)
(a+b) mod c =((a mod c)+(b mod c )) mod c;
(a*b) mod c=((a mod c)*(b mod c)) mod c


欧拉函数模板
(1)直接求小于或等于n,且与n互质的个数:

int Euler(int n) { int ret=n; for(int i=2; i<=sqrt(n); i++) if(n%i==0) { ret=ret/i*(i-1); //先进行除法防止溢出(ret=ret*(1-1/p(i))) while(n%i==0)//防止之后遇到有这个数组成的合数参与 n/=i; } if(n>1)//由于时间复杂度为O(sqrt(n),n在上面的操作中可能被约成了一个质数(或者它本身就是个质数),这里也需要计算在内。【这里没看懂,引别人一句话留着慢慢看http://www.mamicode.com/info-detail-2377639.html】 ret=ret/n*(n-1); return ret; }


筛选模板:求[1,n]之间每个数的质因数的个数
#define size 1000001int euler[size]; void Init(){memset(euler,0,sizeof(euler)); euler[1]=1; for(int i=2; i

代码:
/*#include #include int main(){ int N,ans; while(~scanf("%d",&N)){ ans=N; for(int i=2; i<=sqrt(N); i++) if(N%i==0){ ans=ans/i*(i-1); while(N%i==0)N/=i; } if(N>1)ans=ans/N*(N-1); printf("%d\n",ans); } return 0; } */ #include #include const int MAXN=1000010; int dp[MAXN]; int main(){ memset(dp,0,sizeof(dp)); dp[1]=1; for(int i=2; i



转自:http://www.mamicode.com/info-detail-2377639.html
欧拉函数的扩展
①若n为质数,显然,φ(n) = n - 1
②若n为奇数,有φ(2 * n) = φ(n)
③对于n > 2,所有的φ(n)均为偶数。
④小于n的与n互质的数的和可以表示为φ(n)*n/2
⑤线性同余方程 欧拉函数
文章图片
恒成立,由此还可以引出费马小定理,即当p为质数时,有欧拉函数
文章图片
。这条性质常被应用于求取乘法逆元。
⑥求取最小的m(m > 1),使φ(m) >= n,得到的m应为从n + 1开始的第一个素数。此条是我从欧拉函数表中观察得出的,或许有用,可以参考LightOJ1370。
扩展欧拉定理
求解同余方程a^b ≡ x(mod m)时,b可能会非常大,扩展欧拉定理可以优化其计算。
当gcd(a, m) == 1时,由上方的性质④可以很容易地得出,a^b ≡ a^(b % φ(m)) (mod m)
当gcd(a, m) > 1 且b> φ(m)时,a^b ≡ a^(b % φ(m) + φ(m)) (mod m)
推导过程见https://blog.csdn.net/synapse7/article/details/19610361

    推荐阅读