逆元素 - 杨子说数学
逆元——杨子曰数学
超链接:数学合集
当我们要在代码中做除法,又要对答案取模时,我们会发现 ( a / b ) m o d p (a/b)\ mod\ p (a/b) mod p是不等于 ( a m o d p ) / ( b m o d p ) (a\ mod\ p)/(b\ mod\ p) (a mod p)/(b mod p)的,这那就很讨厌了,它导致我们不能正常地在模一个数下做除法了!
这时候,一个叫逆元(我们高级地称它为inv)的东西就诞生了,它可以帮助我们解决这个问题
先不管这个模数,在小学的时候我们就知道了:
a
/
b
=
a
∗
b
−
1
a/b=a*b^{-1}
a/b=a∗b−1
我们就美滋滋地把一个除法转化成了一个乘法,那么这样我们就可以大胆地模了
那么
b
−
1
b^{-1}
b−1的代数意义是什么捏?
就是:
b
∗
b
−
1
=
1
b*b^{-1}=1
b∗b−1=1
如果放在我们的模数下,它的意义就是:
b
∗
b
−
1
≡
1
(
m
o
d
p
)
b*b^{-1} \equiv 1(mod\ p)
b∗b−1≡1(mod p)
那么现在我们的目标很明确,就是要解这样一个方程:
a
∗
x
≡
1
(
m
o
d
p
)
a*x \equiv 1(mod\ p)
a∗x≡1(mod p)
解出来以后,x就是a在模p下的逆元
求逆元,也就是解这个方程有3种方法,且听我一一道来:
1.费马小定理(条件:p是质数)
不会费马小定理的童鞋,戳我
费马小定理长这样:
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}\equiv1(mod\ p)
ap−1≡1(mod p)
然后我们乘出一个a:
a
∗
a
p
−
2
≡
1
(
m
o
d
p
)
a*a^{p-2}\equiv1(mod\ p)
a∗ap−2≡1(mod p)
哦,有没有发现问题解决,上面那个 式子告诉我们,当p是质数的时候,a在mod p下的逆元就是
a
p
−
2
a^{p-2}
ap−2
然后快速幂搞一搞就好了!
复杂度:O(log p)
int pow(int a,int b,int p){
int ans=1;
while(b){
if (b%2) ans=(ans*a)%p;
b/=2;
a=(a*a)%p;
}
return ans;
}
int inv(int a,int p){
return pow(a,p-2,p);
}
2.扩展欧几里得算法(条件:a和p互质)
机智的你一定发现了:
a
∗
x
≡
1
(
m
o
d
p
)
a*x\equiv1(mod\ p)
a∗x≡1(mod p)是一个模线性方程
也就是我们可以用扩展欧几里得解决(这甚至是一道noip提高组原题:同余方程)
如何求解模线性方程捏?
虽然我在这篇文章里讲过了:一篇文章,但我还要讲一讲:
观察这个方程:
a
∗
x
≡
1
(
m
o
d
p
)
a*x\equiv1(mod\ p)
a∗x≡1(mod p),有没有发现它其实就等价于:
a
∗
x
+
p
∗
y
=
1
a*x+p*y=1
a∗x+p∗y=1
使用扩展欧几里得求逆元的条件是a和p互质(上面标题写了),也就是
g
c
d
(
a
,
p
)
=
1
gcd(a,p)=1
gcd(a,p)=1
那么方程就是:
a
∗
x
+
p
∗
y
=
g
c
d
(
a
,
p
)
a*x+p*y=gcd(a,p)
a∗x+p∗y=gcd(a,p)
那么就和欧几里得算法的方程一模一样了,然后我们再美滋滋地用扩展欧几里得解决(扩展欧几里得?那是什么,戳),完事!
复杂度:O(log p)
int ex_gcd(int a,int b,int &x,int &y){
if(!b) x=1,y=0;
else ex_gcd(b,a%b,y,x),y-=(a/b)*x;
}
int inv(int a,int p){
int x,y;
ex_gcd(a,p,x,y);
x=(x%p+p)%p;//找到最小正整数解
return x;
}
3.线性求1~n的逆元(条件:p是质数)
其实逆元这个东西是可以递推的,神不神奇!
假设我们当前要求的是inv[i],就是i在模p下的逆元:
设
:
p
=
k
∗
i
+
r
(
r
<
i
)
设:p=k*i+r\ \ \ \ \ (r<i)
设:p=k∗i+r (r<i)
我们就可以知道:
k
=
⌊
p
i
⌋
,
r
=
p
m
o
d
i
(
由
于
p
是
质
数
,
S
o
,
r
一
定
大
于
0
)
k=\lfloor\frac{p}{i}\rfloor,r=p\ mod\ i\ \ \ \ \ \ (由于p是质数,So,r一定大于0)
k=⌊ip⌋,r=p mod i (由于p是质数,So,r一定大于0)
我们还可以得到:
k
∗
i
+
r
≡
0
(
m
o
d
p
)
k*i+r\equiv0(mod\ p)
k∗i+r≡0(mod p)
然后捏,我们将同余号两边同时乘上
i
−
1
∗
r
−
1
i^{-1}*r^{-1}
i−1∗r−1(这里的-1次方指的都是逆元):
k
∗
r
−
1
+
i
−
1
≡
0
(
m
o
d
p
)
k*r^{-1}+i^{-1}\equiv0(mod\ p)
k∗r−1+i−1≡0(mod p)
移项:
i
−
1
≡
−
k
∗
r
−
1
(
m
o
d
p
)
i^{-1}\equiv-k*r^{-1}(mod\ p)
i−1≡−k∗r−1(mod p)
然后把k和r代掉:
i
−
1
≡
−
⌊
p
i
⌋
∗
(
p
m
o
d
i
)
−
1
(
m
o
d
p
)
i^{-1}\equiv-\lfloor\frac{p}{i}\rfloor*(p\ mod\ i)^{-1}(mod\ p)
i−1≡−⌊ip⌋∗(p mod i)−1(mod p)
欸,有没有发现就是:
i
n
v
[
i
]
=
−
⌊
p
i
⌋
∗
i
n
v
[
p
m
o
d
i
]
inv[i]=-\lfloor\frac{p}{i}\rfloor*inv[p\ mod\ i]
inv[i]=−⌊ip⌋∗inv[p mod i]
然后我们就完美地推出了逆元的递推公式
噢,对了,由于 1 ≡ 1 − 1 ( m o d p ) 1\equiv1^{-1}(mod\ p) 1≡1−1(mod p),So,初始情况就是inv[1]=1
复杂度O(n)
void get_inv(int n,int p){
inv[1]=1;
for (int i=2;i<=n;i++){
inv[i]=inv[p%i]*(p-p/i)%p;
}
}
参考:
https://blog.****.net/tobeyours/article/details/79619333
http://blog.miskcoo.com/2014/09/linear-find-all-invert
于HG机房