Appearance
若无特殊说明,本章涉及的变量皆为正整数。
定义
若
乘法逆元能够很好地将模运算中的除法转为乘法:
在模运算中,
是整数,并不是 的 次方。
解法
对于整数
cpp
int exGcd(int a, int b, int& x, int& y) {
if(b == 0) { x = 1, y = 0; return a; }
int d = exGcd(b, a % b, x, y);
int t = x; x = y, y = t - a / b * y;
return d;
}
int liEu(int a, int b, int c) { // a·x ≡ c (mod b)
int x, y, d = exGcd(a, b, x, y);
x *= (c / d);
int t = b / d;
return (x % t + t) % t;
}
int inv(int x, int m) {
return liEu(x, m, 1);
}
模为质数的逆元
当
线性求逆元
求
在模 意义下的逆元。
假设已经求出了
设
两边同乘
由于
cpp
inv[1] = 1; // 1 的乘法逆元 = 1
for (int i = 2; i <= n; i ++) {
inv[i] = (- p / i * inv[p % i]) % p;
inv[i] = (inv[i] + p) % p; // 化为正整数
}