? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 乘法逆元

[用途]

求解關于a/b（mod p)的問題

[介紹]

我們假設x為b的乘法逆元,可以將a/b（mod p)轉化為ax(mod)p；根據乘法逆元的定義，在模p的意義下有：bx≡1 (mod) p

如果乘法逆元x存在，b,p一定互素！

[適用條件]

• 當p為素數時，可以使用費馬小定理求解
• 當p為合數時，使用歐拉定理求解
• 不管p是素數還是合數，都可以使用拓展歐幾里得求解（推薦）

?

拓展歐幾里得

對于ax≡1 (mod) p可以化為ax+bp=1;如果乘法逆元x存在，a,p一定互素，即gcd(a,p)=1;反之a,p不互素，則乘法逆元x不存在；而拓展歐幾里得剛好用于求解ax+by=gcd(a,b),我們可以根據gcd(a,b)是否等于1來判斷乘法逆元x是否存在。

#include<iostream> using namespace std; typedef long long LL; LL exgcd(LL a,LL b,LL &x,LL &y) {if(!b){x=1;y=0;return a;}LL gcd=exgcd(b,a%b,y,x);y-=a/b*x;return gcd; } int main() {LL a,b;while(cin>>a>>b){LL x,y;if(exgcd(a,b,x,y)!=1)cout<<"a的乘法逆元不存在"<<endl;else cout<<"a的乘法逆元為: "<<x<<endl; }return 0; }

費馬小定理

當a是正整數，p是素數時，有a^(p-1)≡1 (mod) p,則乘法逆元x=a^(p-2),根據快速冪求解即可

#include<iostream> using namespace std; typedef long long LL; LL ksm(LL x,LL n,LL mod) {x%=mod;LL ans=1;while(n){if(n&1)ans=ans*x%mod;x=x*x%mod;n>>=1;}return ans; } int main() {LL a,mod;while(cin>>a>>mod)cout<<"a的乘法逆元為："<<ksm(a,mod-2,mod)<<endl; return 0; }

?

歐拉定理

有a^phi(p)≡1 (mod) p，a的乘法逆元x即為phi(p)

積性函數：函數f(x)對任意互素的兩個數x1,x2,有f(x1*x2)=f(x1)*f(x2)

完全積性函數：函數f(x)對任意兩個正整數數x1,x2,有f(x1*x2)=f(x1)*f(x2)

對于積性函數有：f(p)=f(p1^k1)*f(p2^k2)*f(p3^k3)....*f(pn^kn),其中p1、p2...pn為不同的素數，k1、k2....kn為非負整數

歐拉函數是積性函數，也有phi(p)=phi(p1^k1)*phi(p2^k2)*phi(p3^k3)....*phi(pn^kn)

對于歐拉函數還有以下結論成立：

結論一：p為素數：phi(p)=p-1;

結論二：p為素數且k是p的倍數：phi(p*k)=phi(k)*p;

結論三：p,q互素：phi(p*q)=phi(p)*phi(q)

結論四：p為素數，k為正整數,phi(p^k)=p^k-p^(k-1)=(p-1)*p^(k-1),

?

歐拉篩法 時間復雜度為O(n)

#include<iostream> #include<cstring> #include<cmath> using namespace std; typedef long long LL; const LL N=1e6+99; LL su[N],phi[N],num; bool vis[N]; void init() {memset(vis,true,sizeof(vis));num=0;vis[0]=vis[1]=false;phi[1]=1; /*phi[1]特例*/ for(LL i=2;i<N;++i){ /*歐拉篩法*/ if(vis[i]){su[++num]=i;phi[i]=i-1; /*結論一*/}for(LL j=1;j<=num&&i*su[j]<N;++j){vis[i*su[j]]=false;if(i%su[j]==0){ /*結論二*/phi[i*su[j]]=phi[i]*su[j];break;}else phi[i*su[j]]=phi[i]*phi[su[j]];/*結論三*/}}/*for(LL i=1;i<=100;++i)cout<<su[i]<<" ";cout<<endl;for(LL i=1;i<=100;++i)cout<<phi[i]<<" ";*/ } int main() {init();return 0; }

一般的，p不會超過int范圍，求phi(p)時如果選擇歐拉篩法打表，時間復雜度為O(n)，很有可能是超時的，所以我們可以選擇時間復雜度為O(√n) (僅僅求單個) 的方法。

另一條重要的定理是算數基本定理：任何一個大于1的自然數 N，可以唯一分解成有限個質數的乘積，即N=(p1^k1)*(p2^k2)*(p3^k3)....(pn^kn),其中p1、p2...pn為不同的素數，k1、k2....kn為非負整數，而對于歐拉函數有

phi(p)=phi(p1^k1)*phi(p2^k2)*phi(p3^k3)....*phi(pn^kn)，利用結論四:p為素數，k為正整數,phi(p^k)=p^k-p^(k-1)=(p-1)*p^(k-1)；再結合篩法(埃式與歐拉都行)求2~√p的素數即可，時間復雜度O(√n)

#include<iostream> #include<cstring> using namespace std; typedef long long LL; const LL N=1e3+99; LL su[N],num; bool vis[N]; void init() {memset(vis,true,sizeof(vis));num=0;vis[0]=vis[1]=false; for(LL i=2;i<=N;++i){ if(vis[i])su[++num]=i;for(LL j=1;j<=num&&i*su[j]<=N;++j){vis[i*su[j]]=false;if(i%su[j]==0)break;}}/*for(LL i=1;i<=100;++i)cout<<su[i]<<" ";cout<<endl;*/ } LL get(LL p) {LL ans=1;for(int i=1;i<=num;++i){if(p%su[i]==0){int j=-1;while(p%su[i]==0){++j; /*求指數j即結論四中的k-1*/ p/=su[i];}while(j--)ans*=su[i]; /*求p^(k-1)*/ ans*=(su[i]-1); /*求(p-1)*p^(k-1)*/if(p==1)break;}}return ans; } int main() {init();LL p;while(cin>>p)cout<<"phi(p)："<<get(p)<<endl; return 0; }

?

?

?

總結

以上是生活随笔為你收集整理的数论-乘法逆元的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。