逆元(Inverse element)就是在mod意義下，不能直接除以一個數，而要乘以它的逆元。
比如a∗b≡1(modp)a∗b≡1(modp)，那麼a，b互為模n意義下的逆元，比如你要算x/a，就可以改成x*b%p
觀察a∗b≡1(modp)a∗b≡1(modp),變形為a∗b+k∗p=1a∗b+k∗p=1，就可以用擴充套件歐幾里得演算法求a了，同時這裡也說明了a和p只有在互素的情況下才存在逆元。
注意
在下面所有的演算法中，最好先把除數取個模再運算。
方法一：擴充套件歐幾里得演算法
原理
a∗b≡1(modp)a∗b≡1(modp)
a∗b+k∗p=1a∗b+k∗p=1
然後a就是我們要求的逆元，最終得到一個正數a的話就要對a mod p，因為a加上mp的時侯k減少mb可以使得等式依然成立。
如果你不想讓逆元為正數，那麼直接返回x也是可以正確的逆元
程式碼
LL exgcd(LL a,LL b,LL &x,LL &y)//擴充套件歐幾里得演算法
{
if(b==0)
x=1,y=0;
return a;
}
LL ret=exgcd(b,a%b,y,x);
y-=a/b*x;
return ret;
LL getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1
LL x,y;
LL d=exgcd(a,mod,x,y);
return d==1?(x%mod+mod)%mod:-1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
注意：返回的時候可以改成(x+mod)%mod，因為擴充套件歐幾里得演算法算出來的x應該不會太大.
效能分析:
時間複雜度:O(logn)（實際是斐波那契數列）
適用範圍：只要存在逆元即可求，適用於個數不多但是mod很大的時候，也是最常見的一種求逆元的方法。
方法二:費馬小定理/尤拉定理
費馬小定理：若p為素數，則有ap−1≡1(modp)ap−1≡1(modp)
ap−2∗a≡1(modp)ap−2∗a≡1(modp)
ap−2ap−2就是a在mod p意義下的逆元啦。
尤拉定理：若a、p互素，則有aφ(p)≡1(modp)aφ(p)≡1(modp)(費馬小定理的一般形式)
aφ(p)∗a≡1(modp)aφ(p)∗a≡1(modp)
aφ(p)−1aφ(p)−1就是a在mod p意義下的逆元啦。
LL qkpow(LL a,LL p,LL mod)
LL t=1,tt=a%mod;
while(p)
if(p&1)t=t*tt%mod;
tt=tt*tt%mod;
p>>=1;
return t;
LL getInv(LL a,LL mod)
return qkpow(a,mod-2,mod);
效能分析：
O(logmod)
適用範圍：一般在mod是個素數的時候用，比擴歐快一點而且好寫。
但是如果是合數，相信一般沒人無聊到去算個尤拉函式。
方法三：遞推求逆元
p是模數，i是待求的逆元，我們求的是i−1i−1在mod p意義下的值
p=k∗i+rp=k∗i+r令 r < i,則k=p/i,r=p%i
k∗i+r≡0(modp)k∗i+r≡0(modp)
k∗r−1+i−1≡0(modp)k∗r−1+i−1≡0(modp)
i−1≡−k∗r−1(modp)i−1≡−k∗r−1(modp)
i−1≡−p/i∗inv[pmodi]i−1≡−p/i∗inv[pmodi]
嗯。。好難看的公式
說白了就是:inv[i]=-(mod/i)*inv[i%mod]
然後邊界是inv[1]=1
這不僅為我們提供了一個線性求逆元的方法，也提供了一種O(logmod)求逆元的方法
線性求逆元
LL inv[mod+5];
void getInv(LL mod)
inv[1]=1;
for(int i=2;i<mod;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
注意：
呼叫前要先預處理
呼叫的時候要先對除數取mod
時間複雜度O(n)
適用範圍：mod數是不大的素數而且多次呼叫，比如盧卡斯定理。
遞迴求逆元
LL inv(LL i)
if(i==1)return 1;
return (mod-mod/i)*inv(mod%i)%mod;
效能分析
時間複雜度:O(logmod)
好像找到了最簡單的演算法了！！
適用範圍： mod數是素數，所以並不好用，比如中國剩餘定理中就不好使，因為很多時候可能會忘記考慮mod數是不是素數。
逆元(Inverse element)就是在mod意義下，不能直接除以一個數，而要乘以它的逆元。
比如a∗b≡1(modp)a∗b≡1(modp)，那麼a，b互為模n意義下的逆元，比如你要算x/a，就可以改成x*b%p
觀察a∗b≡1(modp)a∗b≡1(modp),變形為a∗b+k∗p=1a∗b+k∗p=1，就可以用擴充套件歐幾里得演算法求a了，同時這裡也說明了a和p只有在互素的情況下才存在逆元。
注意
在下面所有的演算法中，最好先把除數取個模再運算。
方法一：擴充套件歐幾里得演算法
原理
a∗b≡1(modp)a∗b≡1(modp)
a∗b+k∗p=1a∗b+k∗p=1
然後a就是我們要求的逆元，最終得到一個正數a的話就要對a mod p，因為a加上mp的時侯k減少mb可以使得等式依然成立。
如果你不想讓逆元為正數，那麼直接返回x也是可以正確的逆元
程式碼
LL exgcd(LL a,LL b,LL &x,LL &y)//擴充套件歐幾里得演算法
{
if(b==0)
{
x=1,y=0;
return a;
}
LL ret=exgcd(b,a%b,y,x);
y-=a/b*x;
return ret;
}
LL getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1
{
LL x,y;
LL d=exgcd(a,mod,x,y);
return d==1?(x%mod+mod)%mod:-1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
注意：返回的時候可以改成(x+mod)%mod，因為擴充套件歐幾里得演算法算出來的x應該不會太大.
效能分析:
時間複雜度:O(logn)（實際是斐波那契數列）
適用範圍：只要存在逆元即可求，適用於個數不多但是mod很大的時候，也是最常見的一種求逆元的方法。
方法二:費馬小定理/尤拉定理
原理
費馬小定理：若p為素數，則有ap−1≡1(modp)ap−1≡1(modp)
ap−2∗a≡1(modp)ap−2∗a≡1(modp)
ap−2ap−2就是a在mod p意義下的逆元啦。
尤拉定理：若a、p互素，則有aφ(p)≡1(modp)aφ(p)≡1(modp)(費馬小定理的一般形式)
aφ(p)∗a≡1(modp)aφ(p)∗a≡1(modp)
aφ(p)−1aφ(p)−1就是a在mod p意義下的逆元啦。
程式碼
LL qkpow(LL a,LL p,LL mod)
{
LL t=1,tt=a%mod;
while(p)
{
if(p&1)t=t*tt%mod;
tt=tt*tt%mod;
p>>=1;
}
return t;
}
LL getInv(LL a,LL mod)
{
return qkpow(a,mod-2,mod);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
效能分析：
O(logmod)
適用範圍：一般在mod是個素數的時候用，比擴歐快一點而且好寫。
但是如果是合數，相信一般沒人無聊到去算個尤拉函式。
方法三：遞推求逆元
原理
p是模數，i是待求的逆元，我們求的是i−1i−1在mod p意義下的值
p=k∗i+rp=k∗i+r令 r < i,則k=p/i,r=p%i
k∗i+r≡0(modp)k∗i+r≡0(modp)
k∗r−1+i−1≡0(modp)k∗r−1+i−1≡0(modp)
i−1≡−k∗r−1(modp)i−1≡−k∗r−1(modp)
i−1≡−p/i∗inv[pmodi]i−1≡−p/i∗inv[pmodi]
嗯。。好難看的公式
說白了就是:inv[i]=-(mod/i)*inv[i%mod]
然後邊界是inv[1]=1
這不僅為我們提供了一個線性求逆元的方法，也提供了一種O(logmod)求逆元的方法
程式碼
線性求逆元
LL inv[mod+5];
void getInv(LL mod)
{
inv[1]=1;
for(int i=2;i<mod;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
1
2
3
4
5
6
7
1
2
3
4
5
6
7
注意：
呼叫前要先預處理
呼叫的時候要先對除數取mod
效能分析：
時間複雜度O(n)
適用範圍：mod數是不大的素數而且多次呼叫，比如盧卡斯定理。
遞迴求逆元
LL inv(LL i)
{
if(i==1)return 1;
return (mod-mod/i)*inv(mod%i)%mod;
}
1
2
3
4
5
1
2
3
4
5
效能分析
時間複雜度:O(logmod)
好像找到了最簡單的演算法了！！
適用範圍： mod數是素數，所以並不好用，比如中國剩餘定理中就不好使，因為很多時候可能會忘記考慮mod數是不是素數。