定义
$a$ 的逆元写作 $a^{-1}$。
我们定义 $a \times a^{-1} \equiv 1 \pmod p$。
计算方法
费马小定理
知识链接
费马小定理结论：
对于一个素数 $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;
}