乘法逆元

對于縮系中的元素，每個數a均有唯一的與之對應的乘法逆元x，使得ax≡1(mod n)
一個數有逆元的充分必要條件是gcd(a,n)=1，此時逆元唯一存在?
逆元的含義：模n意義下，1個數a如果有逆元x，那么除以a相當于乘以x。

?

下面給出求逆元的幾種方法：

1.擴展歐幾里得

給定模數m，求a的逆相當于求解ax=1(mod m)
這個方程可以轉化為ax-my=1?
然后套用求二元一次方程的方法，用擴展歐幾里得算法求得一組x0,y0和gcd?
檢查gcd是否為1?
gcd不為1則說明逆元不存在?
若為1，則調整x0到0~m-1的范圍中即可

PS：這種算法效率較高，常數較小，時間復雜度為O(ln n)

?

?

2.費馬小定理

在模為素數p的情況下，有費馬小定理?
a^(p-1)=1（mod p）?
那么a^(p-2)=a^-1(mod p)?
也就是說a的逆元為a^(p-2)

而在模不為素數p的情況下，有歐拉定理?
a^phi(m)=1（mod m） (a⊥m)?
同理a^-1=a^(phi(m)-1)

因此逆元x便可以套用快速冪求得了x=a^(phi(m)-1)

但是似乎還有個問題？如何判斷a是否有逆元呢??

檢驗逆元的性質，看求出的冪值x與a相乘是否為1即可

PS:這種算法復雜度為O（log2N）在幾次測試中，常數似乎較上種方法大

當p比較大的時候需要用快速冪求解

?

當模p不是素數的時候需要用到歐拉定理

a^phi(p)≡1 ? ? ? ? ? ? ? (mod p)

a*a^(phi(p)-1)≡1 ? ? ?(mod p)

a^(-1)≡a^(phi(p)-1)? (mod p)

所以
時間復雜度即求出單個歐拉函數的值

(當p為素數的時候phi(p)=p-1,則phi(p)-1=p-2可以看出歐拉定理是費馬小定理的推廣)

PS：這里就貼出歐拉定理的板子，很少會用歐拉定理求逆元

?

?

3.特殊情況

一：

當N是質數，?
這點也很好理解。當N是質數，0 < a < N時，，則a肯定存在逆元。?
而解出的就滿足，故它是a的逆元。

在CF 696C，

求解就灰常方便了…

二：

求逆元一般公式(條件b|a)

ans=a/bmodm=amod(mb)/b

公式證明：

PS:實際上a mod (bm)/b這種的對于所有的都適用，不區分互不互素,而費馬小定理和擴展歐幾里得算法求逆元是有局限性的，它們都會要求與互素，如果a與m不互素，那就沒有逆元，這個時候需要a mod (bm)/b來搞（此時就不是逆元的概念了）。但是當a與m互素的時候，bm可能會很大，不適合套這個一般公式，所以大部分時候還是用逆元來搞

4.逆元打表

?

?

有時會遇到這樣一種問題，在模質數p下，求1~n逆元 n< p（這里為奇質數）。可以O(n)求出所有逆元，有一個遞推式如下

?

???????????????????

?

它的推導過程如下，設，那么

?

???? ??

?

對上式兩邊同時除，進一步得到

?

???????

?

再把和替換掉，最終得到

?

???????

?

初始化，這樣就可以通過遞推法求出1->n模奇素數的所有逆元了。

?

另外有個結論模的所有逆元值對應中所有的數，比如，那么對應的逆元是。

typedef long long ll; const int N = 1e5 + 5; int inv[N];void inverse(int n, int p) {inv[1] = 1;for (int i=2; i<=n; ++i) {inv[i] = (ll) (p - p / i) * inv[p%i] % p;} }

?

轉自：https://blog.csdn.net/guhaiteng/article/details/52123385

更多例題：https://blog.csdn.net/acdreamers/article/details/8220787

?

線性求逆元? ?題目

ll c(int r,int l) {if (r<l) return 0;return jie[r]*inv[l]%mod*inv[r-l]%mod; } int main() {jie[1] = 1;jie[0] = 1;inv[1] = 1;inv[0] = 1;for(int i = 2; i<=MAX-1; i++) jie[i] = (jie[i-1] * i)%mod;for(int i = 2; i<=MAX-1; i++) {inv[i] = (mod - mod/i*inv[mod%i]%mod)%mod;} //這兩個求逆元的公式都可以使用 // for (int i=2; i<MAX; i++) { // inv[i]=inv[mod%i]*(mod-mod/i)%mod; // } //預處理逆元的前綴積for (int i=2; i<MAX; i++) inv[i]=inv[i-1]*inv[i]% mod;

線性求逆元??題目

const ll mod = 1000000000+7; const ll N = 300000+5; const ll M = 3e5+3; int n; ll fac[1000005]; //階乘 ll inv_of_fac[1000005]; //階乘的逆元 int a[15]; ll dp[150][12]; ll qpow(ll x,ll n) {ll ret=1;for(; n; n>>=1){if(n&1) ret=ret*x%mod;x=x*x%mod;}return ret; } void init() {fac[1]=1;for(int i=2; i<=M; i++)fac[i]=fac[i-1]*i%mod;inv_of_fac[M]=qpow(fac[M],mod-2);for(int i=M-1; i>=0; i--)inv_of_fac[i]=inv_of_fac[i+1]*(i+1)%mod;//inv_of_fac[i]=qpow(fac[i],mod-2);//為什么不行啊 //也行 } ll C(ll a,ll b) {if(b>a) return 0;if(b==0) return 1;return fac[a]*inv_of_fac[b]%mod*inv_of_fac[a-b]%mod; }

咖啡雞的求逆元：

#include<bits/stdc++.h> using namespace std; const int maxn=4005; const int E=2000; typedef long long ll; const ll M=1000000007; ll f[maxn],nf[maxn],inv[maxn],dp[2][maxn]; int n,m; ll C(ll x,ll y){return f[x]*nf[y]%M*nf[x-y]%M; } ll K(ll x){return C(x*2,x)*inv[x+1]%M; } void add(ll &x,ll y){x+=y; if (x>=M) x-=M; } int main(){inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-(M/i)*inv[M%i]%M;f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=f[i-1]*i%M,nf[i]=nf[i-1]*inv[i]%M;return 0; }

?

總結

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

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