浅谈模质数意义下的乘法逆元
参考文章 www.luogu.org/blog/zyxxs/post-xiao-yi-jiang-tan-qian-tan-sheng-fa-ni-yuan
什么是乘法逆元
若整数 \(b,m\)
互质,并且 \(b|a\)
,若存在一个整数 \(x\)
,使得 \(a / b \equiv a \ast x (mod \text{ } m)\)
,称 \(x\)
为
\(b\)
的模 \(m\)
乘法逆元
。
乘法逆元的用处
有时候,我们需要求 \(a/b \text{ } mod \text{ } p\)
,用朴素的方法,我们只能在 \(a\)
上不断加 \(p\)
,直到它能被 bb 整除为止,当 \(a,b,p\)
都很大的时候,自然是凉凉了。这时,我们就可以用逆元方便的求解了。
乘法逆元的求法
进入到了本文最关键的部分,如何求乘法逆元?
费马小定理
费马小定理:当 \(p\)
是质数的时候,$a^{p-1} \equiv 1 (mod \text{ } p) $
那么将 \(a^{p-1}\)
拆开来,就得到了 \(a \ast a^{p-2} \equiv (mod \text{ } p)\)
所以, \(a^{p-2}\)
就是 \(a\)
模 \(p\)
意义下的乘法逆元。
缺点:用快速幂计算,当 \(p\)
比较大的时候,速度比较慢。
代码:
#include #include #include using namespace std; typedef long long ll; ll n, p; ll ksm(ll a, ll b) { ll ans = 1; for (; b; b >>= 1) { if (b & 1) ans = ans * a % p; a = a * a % p; } return ans; } int main() { freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); cin >> n >> p; for (int i = 1; i <= n; ++i) { printf("%lld\n", ksm(i, p - 2)); } return 0; }
扩展欧几里得算法
求 \(a \ast x \equiv 1 (mod \text{ } m)\)
的解 \(inv(x)\)
,等价于求解 \(a \ast x + b \ast y =1\)
。用扩展欧几里得算法求出一组特解 \(x_0, y_0\)
,则 \(x_0\)
是原方程的一个解,而方程的通解则为所有模 \(m\)
与 \(x_0\)
同余的整数,通过取模操作把解的范围移动到 \(1~p\)
之间即可。
代码:
#include #include #include using namespace std; typedef long long ll; ll n, p; void exgcd(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1, y = 0; return; } exgcd(b, a % b, x, y); ll z = x; x = y, y = z - y * (a / b); return; } int main() { cin >> n >> p; for (int i = 1; i <= n; ++i) { ll x, y; exgcd(i, p, x, y); x = (x % p + p) % p; cout << x << endl; } return 0; }
线性递推(可以求多个)
这是一个神奇的过程……
假设我们现在要求 \(k\)
的乘法逆元,
令 \(a \ast k + b = p\)
\[b \ast inv(b) \equiv 1 (mod \text{ } p)\]
把 \(b=p-a\ast k\)
代入,可以得到
\[(p-ak)\ast inv(b) \equiv 1 (mod \text{ } p)\]
那么
\[p \ast inv(b) – a \ast k \ast inv(b) \equiv 1 (mod \text{ } p)\]
在 \((mod \text{ } p)\)
的意义下, \(p \equiv 0 (mod \text{ } p)\)
,所以 \(p \ast inv(b)\)
可以直接去掉
\[-a \ast k \ast inv(b) \equiv 1 (mod \text{ } p)\]
观察 \(a \ast k + b = p\)
可以发现, \(a=\lfloor p/k \rfloor\)
, \(b=p \mod k\)
\[-(p/k) \ast inv(p \text{ } mod \text{ } k) \ast k \equiv 1 (mod \text{ } p)\]
即
\[-(p/k) \ast inv(p \text{ } mod \text{ } k) \equiv inv(k) (mod \text{ } p)\]
这样,我们就得了递推式,在实际的代码实现中得加上 \(p\)
来去掉负号,也就是
\[(p-p/k) \ast inv(p \text{ } mod \text{ } k) \equiv inv(k) (mod \text{ } p)\]
代码:
#include #include #include #include using namespace std; typedef long long ll; ll n, p, inv[maxn]; int main() { freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); cin >> n >> p; inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = (ll)(p - p / i) * inv[p % i] % p; for (int i = 1; i <= n; ++i) printf("%lld\n", inv[i]); return 0; }