乘法逆元小结
乘法逆元在算法竞赛中具有十分重要的应用。
逆元定义
对于正整数 a 和 m ,如果有 ax\equiv 1\pmod{m} ,那么把同余方程中 x 的最小正整数解叫做 a 模 m 的逆元,记作a^{-1},也可以称 x 为 a 在模 m 意义下的倒数。
所以对于 \frac{a}{b} \pmod p ,我们可以求出 b 模 p 的逆元,然后乘以 a ,就可以算出结果了。
当a⊥m(即 a 与 m 互质)时,a 在模 m 意义下存在逆元。
以下介绍求逆元的几种方法,每种方法均应理解并掌握。
扩展欧几里得求解逆元
因为需要解 ax\equiv1 \pmod m,即
ax+my =1
的 x 的最小正整数解
直接用扩欧即可
该方法不要求 m 为质数
void exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
ll x, y;
exgcd (a, p, x, y);
x = (x % p + p) % p;
printf ("%d\n", x); //x是a在mod p下的逆元
}
利用费马小定理求解逆元
费马小定理(Fermat’s little theorem)是数论中的一个重要定理,在1636年提出。如果 p 是一个质数,而整数 a 不是 p 的倍数,则有
a^{p-1}≡1 \pmod p
解 ax\equiv1 \pmod m,此方法要求 m 为质数。
因为有
a^{m-1}\equiv1 \pmod m
所以知道
a*a^{m-2}\equiv1 \pmod m
故
x=a^{m-2}
利用快速幂求得即可。
线性递推求逆元
首先有 1 关于 m 的逆元为 1 ,即 1^{-1}\equiv1 \pmod m
然后对于数 i ,有
p=\lfloor \frac{p}{i} \rfloor *i +p\bmod i
我们记 \lfloor \frac{p}{i} \rfloor 为 k ,p \bmod i 为 r
有
k_i+r \equiv0 \pmod p
等式两边同乘 i^{-1} 和 r^{-1} ,得
k_r^{-1}+i^{-1}\equiv0 \pmod p
于是有
i^{-1}\equiv-k*r^{-1}\pmod p
就可以递推出 i 的逆元了
inv[1]=1;
for( int i = 2; i <= n; ++i )
inv[i] = - (p/i) * inv[p % i] % p
考虑到逆元取正数,一般写成
inv[1]=1;
for( int i = 2; i <= n; ++i )
inv[i] = (p- p/i) * inv[p % i] % p ;
0 条评论