定义

$a$ 的逆元写作 $a^{-1}$。

我们定义 $a \times a^{-1} \equiv 1 \pmod p$。

计算方法

费马小定理

知识链接

• 欧拉定理 & 费马小定理 – OI Wiki (oi-wiki.org)

费马小定理结论：

对于一个素数 $p$，如果 $\gcd(p, a) = 1$，那么 $a^{p – 1} \equiv 1\pmod p$。

我们可以通过这条结论推出：
$$
a \times a^{p – 2} \equiv 1 \pmod p
$$
也就是说
$$
a^{-1} = a^{p – 2} \pmod p
$$

代码（求单个数的逆元）

#include <bits/stdc++.h>
 
using namespace std;
/*
*/
#define int long long
#define ll int 
ll p(ll a, ll b, ll q) {
    // cout << a << " " << b << " " << q << "\n";
    if (b == 0) return 1ull;
    else if (b % 2 == 1) return ((a % q) * p(a, b - 1ull, q)) % q;
    else if (b % 2 == 0) {
        ll t = p(a, b / 2ull, q) % q;
        return (t * t) % q;
    } 
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    cout << p(n, q - 2, q);
    return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

代码（求多个数）

也是 P5431 【模板】模意义下的乘法逆元 2 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 的代码。

#include <bits/stdc++.h>
 
using namespace std;
/*
*/
#define int long long
#define ll int 
typedef long long LL;
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;
}
template <typename T>
inline void fprint(T x)//快输
{
    if(x < 0)
    {
        putchar(45);
        x = -x;
    }
    if(x > 9)
    {
        fprint(x / 10);
    }
    putchar(x % 10 + 48);
}
ll p(ll a, ll b, ll q) {
    int res = 1;
    while (b) {
        if (b % 2 == 1) res = res * a % q;
        a = a * a % q;
        b /= 2;
    }
    return res;
}
int f[10000005];
int inf[10000005];
int m[10000005];
int a[10000005];
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q, k; 
    read(n);
    read(q);
    read(k);
    // cout << n;
    for (int i = 1; i <= n; i ++) read(a[i]);
    f[0] = 1;
    for (int i = 1; i <= n; i ++) {
        f[i] = f[i - 1] * a[i] % q;
    }
    inf[n] = p(f[n], q - 2, q);
    for (int i = n - 1; i >= 0; i --) {
        inf[i] = (inf[i + 1] * a[i + 1]) % q;
    }
    int ans = 0;
    int cnt = 1;
    for (int i = 1; i <= n; i ++) {
        cnt = (k * cnt) % q;
        ans = (ans + cnt * inf[i] % q * f[i - 1] % q) % q;
    }
    fprint(ans);
    return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

扩展欧几里得（EXGCD）

知识链接

• 裴蜀定理 – OI Wiki (oi-wiki.org)

• 扩展欧几里得 – OI Wiki (oi-wiki.org)

实现（直接套用 OI-Wiki 的）