一、乘法逆元

如線性同余方程 $ax\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}b)$ 的解 $x$ 稱作 $a$ 在模 $b$ 下的逆元，記作 $x=a^{?1}$。

二、乘法逆元存在的條件

根據線性同余方程組解存在的條件，當且僅當 $\gcd (a,b)=1$ 時，$a$ 在模 $b$ 下存在逆元。

三、求解逆元

1. 擴展歐幾里得算法

使用擴展歐幾里得算法可以在 $O(\log b)$ 的時間復雜度下求出單個數的逆元。
求解線性同余方程 $ax\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}b)$ 即可。

void exgcd(long long a, long long b, long long &x, long long &y){if (!b){x = 1, y = 0;return ;}exgcd(b, a % b, y, x);y -= (a / b) * x; } long long get_inv(long long a, long long p){long long x, y;exgcd(a, p, x, y);if (x < 0) x += p;return x; }

2. 快速冪

使用快速冪可以在 $O(\log n)$ 的時間復雜度下求出單個數的逆元（模數應為質數）。
當 $b$ 為質數時，由費馬小定理得 $a^{b?1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}b)$ ，因此 $a\times a^{b?2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}b)$ ，即 $a$ 的逆元為 $a^{b?2}$ 。代碼如下：

long long qPow(long long a, long long b){long long ret = 1;for (; b; b >>= 1){if (b & 1) ret = (ret * a) % p;a = (a * a) % p;}return ret; }

3. 線性求逆元

使用線性求逆元的方法可以在 $O(b)$ 的時間復雜度下求出 $1$ ~ $b?1$ 所有數在模 $b$ 下的逆元。
從 $1$ 到 $b?1$ 遞推。
① $1$ 的逆元為 $1$
② 設當前數為 $i$ ，且 $b=ki+r(r<i)$ ，則 $b\mathrm{m}\mathrm{o}\mathrm{d}i=r$ 。
在模 $b$ 意義下：
$$ki+r\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}b)$$

兩邊同時乘以 $i^{?1}{r}^{?1}$ 得：
$$k{r}^{?1}+i^{?1}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}b)$$

移項整理：
$$i^{?1}\equiv ?k{r}^{?1}\equiv ??\frac{b}{i}?(b\mathrm{m}\mathrm{o}\mathrm{d}i{)}^{?1}(\mathrm{m}\mathrm{o}\mathrm{d}b)$$

由于 $b\mathrm{m}\mathrm{o}\mathrm{d}i<i$ ，因此已知，可以 $O(1)$ 遞推。代碼如下（Luogu 3811 【模板】 乘法逆元）：

#include<bits/stdc++.h> using namespace std; const int maxn = 3e6 + 5; int n, p; int inv[maxn]; int main(){ios::sync_with_stdio(false);cin.tie(0);cin >> n >> p;inv[1] = 1;for (int i = 2; i <= n; i ++) inv[i] = (p - (p / i)) * inv[p % i] % p;for (int i = 1; i <= n; i ++) cout << inv[i] << '\n';return 0; }

4. 線性求逆元（任意）

接下來介紹一種可以在幾乎線性的時間內求出給出數列 $\{a_n\}$ 中所有數在模 $b$ 意義下的逆元的方法。
首先計算 $\{a_i\}$ 的前綴積，記為 $\{su{m}_n\}$ ，即 $su{m}_i={\Pi }_{j=1}^i{a}_j$ 。其次計算 $su{m}_n$ 的逆元，記為 $inv{s}_n$ 。將 $inv{s}_n$ 倒推求出每一個前綴積的逆，記作 $\{inv{s}_n\}$ ，遞推公式為：
$$inv{s}_{i?1}=inv{s}_i?a_i$$

有了兩個數組，就可以據此得出所有數的逆元 $\{in{v}_i\}$ ：
$$in{v}_i=inv{s}_{i?1}\times su{m}_i$$

代碼如下（Luogu 5431 【模板】 乘法逆元2）：

/*提示：題目卡常，需要使用快讀 */ #include<bits/stdc++.h> using namespace std; const int maxn = 5e6 + 5;long long n, p, k; long long a[maxn], sum[maxn], invs[maxn];template <typename T> inline void read(T &x){char c;x = 0;int fu = 1;c = getchar();while(c > 57 || c < 48){if(c == 45) fu = -1;c = getchar();}while(c <= 57 && c >= 48){x = (x << 3) + (x << 1) + c - 48;c = getchar();}x *= fu; }long long qPow(long long a, long long b){long long ret = 1;for (; b; b >>= 1){if (b & 1) ret = (ret * a) % p;a = (a * a) % p;}return ret; }int main(){read(n), read(p), read(k);for (int i = 1; i <= n; i ++) read(a[i]);sum[0] = 1;for (int i = 1; i <= n; i ++) sum[i] = sum[i - 1] * a[i] % p;invs[n] = qPow(sum[n], p - 2);for (int i = n - 1; i >= 1; i --) invs[i] = invs[i + 1] * a[i + 1] % p;long long mulk = 1, ans = 0;for (int i = 1; i <= n; i ++){mulk = mulk * k % p;ans = (ans + mulk * (invs[i] * sum[i - 1] % p) % p) % p;}printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的乘法逆元学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。