浅谈模质数意义下的乘法逆元
- 2019 年 10 月 3 日
- 筆記
参考文章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 <algorithm> #include <cstdio> #include <iostream> 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("%lldn", 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 <algorithm> #include <cmath> #include <iostream> 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-aast 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 <algorithm> #include <cmath> #include <cstdio> #include <iostream> 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("%lldn", inv[i]); return 0; }