学习：数学----欧拉定理与扩展欧拉定理

佚名 5年前 (2019-04-30) 算法 1865人围观抢沙发百度已收录

欧拉定理和扩展欧拉定理可以解决形如5^{100000000000000000000}等大数幂取模或者求a^x mod n=1的大于1的最小x值等一类问题，其中欧拉函数占巨大的重要性，有效的将复杂的大数幂取模问题转化为简单的大数取模和快速幂问题，下面就来介绍一下基本的欧拉定理和扩展欧拉定理
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

1.欧拉函数的定义

欧拉函数Φ(n)指1至n以内，与n互质的数的个数

当n比较小时，可以通过从前到后遍历的方法计算Φ(n)

对于欧拉函数Φ(n)，还有更简单的计算方法。

假如n可以通过分解质因子得到n的质因子p1,p2,p3.....pn；

那么

　　Φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*.....*(1-1/pn)

特别的，当n=p^r(p为质数)时（p是n的唯一质因子）

　　Φ(n)=p^r-count(p,2p,3p....p^r)=n*(1-1/p) (证明：由于n分解质因子只有p这一个质因子，故n以内与n不互质的数为p的倍数)

当n=p1^r1p2^r2时（p1和p2是n的所有质因子）

　　含有p1的因子为p1,2p1.....p2^r2p1^r1-1,p2^r2p1^r1，一共n/p1个；

　　含有p2的因子为p2,2p2.....p1^r1p2^r2-1,p1^r1p2^r2，一共n/p2个；

　　既含有p1又含有p2的因子为p1p2,2p1p2,3p1p2.....p1^r1-1p2^r2-1，一共n/p1p2个；

　　根据容斥定理可知与n不互质数的个数k为n/p1+n/p2-/p1p2；

　　那么Φ(n)=n-k=n*(1-1/p1)*(1-1/p2);

因此可以推广到n=p1^r1p2^r2....pn^rn

 1 ll getDivisor(){
 2     ll sum=p;
 3     int i;
 4     for(i=2;i*i<=p;i++){
 5         if(p%i==0)    sum=(long long)sum*(1-1.0/i);
 6         while(p%i==0)    p=p/i;
 7     }
 8     if(p!=1)    sum=(long long)sum*(1-1.0/p);
 9     return sum;//sum为欧拉函数的值
10 }

求欧拉函数关于p的值

2.欧拉函数的性质

1）当n为质数时　　Φ(n)=n-1

2）当m与n互质时　　Φ(mn)=Φ(n)*Φ(m)

3）当n为质数时　　Φ(2n)=Φ(n)

例如

　　Φ(6)=Φ(3)=2　或Φ(6)=Φ(3)*Φ(2)=2*1=2

3.欧拉定理

若n与a互质，则a^Φ(n)≡1(mod n)

首先来解释一下 a^Φ(n)≡1(mod n) 是什么意思：

　　a^Φ(n)≡1(mod n) 等价于 a^Φ(n) mod n==1 mod n

应用：可以解决a^x=1(mod n)或a^x mod n=1 mod n的最小x的值的问题

　　由于最小x一定小于等于Φ(n)，则令Φ(n)=t*x+b，但由于我们算的x是最小的x，故b等于0，可以得到Φ(n)是x的倍数，因此只要遍历Φ(n)的所有大于log_an因数，直到找到一个因数k使得a^k≡1(mod n)成立，则k就是最小的x。

比如让你求4^xmod 3=1的最小x值：

　　4与3本身互质，最小x一定小于等于Φ(3)=2，由于2的大于log₄3的最小因数为1使得4^xmod 3=1成立，故x最小取1

特别的，当n是质数时，a^x=1(mod n)的最小x值为n-1

4.扩展欧拉定理

一个公式：a^x mod n≡a^{x mod Φ(n)+Φ(n)} mod n （n与x与a无需满足任何条件）

应用：运用扩展欧拉定理可以解决大数幂求模的问题，将利用大数求余很大的x转化为约等于Φ(n)的一个数，然后可以利用快速幂的方法得到结果！

如让你求4^{9876543210213657854521} mod 12345的值：

　　可以通过分解质因子方法得到Φ(12345)=6576，再利用大数求余求9876543210213657854521 mod 6576=569，再用快速幂求4^569+6576mod 12345=9319

 1 #include <iostream>
 2 #include <algorithm> 
 3 #include <string>
 4 #include <sstream>
 5 #define ll1 (ll)1
 6 using namespace std;
 7 typedef long long ll;
 8 stringstream stream;
 9 ll p,divisor,pow1; 
10 string str;
11 int t;
12 ll qSort(){
13     ll x=4,sum=1;
14     while(pow1!=0){
15         if(pow1%2!=0)    sum=sum*x%p;
16         pow1=pow1>>1;
17         x=x*x%p;
18     }
19     return sum;
20 }
21 ll getPow(){
22     stream<<str;
23     ll sum=0;
24     char c;
25     while(stream>>c)
26         sum=(10*sum+c-'0')%divisor;
27     stream.clear();
28     return sum+divisor;
29 }
30 ll getDivisor(){
31     ll sum=p;
32     int i;
33     ll p1=p;
34     for(i=2;i*i<=p1;i++){
35         if(p1%i==0)    sum=ll1*sum*(1-1.0/i);
36         while(p1%i==0)    p1=p1/i;
37     }
38     if(p1!=1)    sum=ll1*sum*(1-1.0/p1);
39     return sum;
40 }
41 int main(){
42     cin>>t;
43     while(t--){
44         cin>>str>>p;
45         divisor=getDivisor();
46         pow1=getPow();
47         cout<<qSort()%p<<endl;
48     }
49     return 0;
50 }

求4的n次方对p取模的代码

5.总结代码

扩展欧拉定理求aⁿmod p代码：

 1 #include <iostream>
 2 #include <string>
 3 #include <sstream>
 4 using namespace std;
 5 long long getOula_function(long long _mod){
 6     long long i,sum=_mod;
 7     for(i=2;i*i<=_mod;i++){
 8         if(!(_mod%i))    sum=(long long)sum*(1.0-1.0/i);
 9         while(!(_mod%i))    _mod/=i;
10     }
11     if(_mod!=1)    sum=(long long)sum*(1.0-1.0/_mod);
12     return sum;
13 }
14 long long getDivisor_function(string _str,long long _oula){
15     char c;
16     long long sum=0;
17     stringstream _stream;
18     _stream<<_str;
19     while(_stream>>c)    sum=(10*sum+c-'0')%_oula;
20     _stream.clear();    
21     return sum+_oula;
22 }
23 long long qPow_function(long long _x,long long _divisor,long long _mod){
24     long long sum=1;
25     while(_divisor){
26         if(_divisor&1)    sum=sum*_x%_mod;
27         _divisor=_divisor>>1;
28         _x=_x*_x%_mod;
29     }
30     return sum;
31 }
32 long long pow_bigmod(long long _x,string _str,long long _mod){
33     long long _oula=getOula_function(_mod);
34     long long _divisor=getDivisor_function(_str,_oula);
35     return qPow_function(_x,_divisor,_mod)%_mod;
36 }

扩展欧拉公式求大数幂模

使用说明：首先放到代码里面，在main函数中输入pow_bigmod(long long a,string n,long long p),即可返回aⁿ mod p的值

欧拉定理求a^x≡1(mod n)最小x代码：

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 long long getOula_function(long long _mod){
 5     long long i,sum=_mod;
 6       for(i=2;i*i<=_mod;i++){
 7         if(!(_mod%i))    sum=(long long)sum*(1.0-1.0/i);
 8         while(!(_mod%i))    _mod/=i;
 9     }
10     if(_mod!=1)    sum=(long long)sum*(1.0-1.0/_mod);
11     return sum;
12 }
13 long long getMinDiv(long long _base,long long _mod){
14     long long _divisor=getOula_function(_mod);
15     double _flag=log(_mod)/log(_base);
16     for(long long i=(long long)_flag+1;i<=_divisor;i++)
17         if(!(_divisor%i))    return i;
18 }