定义
$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
$$ #### 代码（求单个数的逆元） ```cpp #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)](https://www.luogu.com.cn/problem/P5431) 的代码。 ```cpp #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)](https://oi-wiki.org/math/number-theory/bezouts/) - [扩展欧几里得 - OI Wiki (oi-wiki.org)](https://oi-wiki.org/math/number-theory/gcd/#扩展欧几里得算法) ### 实现（直接套用 OI-Wiki 的）
评论 (0)