int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int ans = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * x;
return ans;
}
然后来看一道例题。
P1082 同余方程
求解
ax\equiv 1\pmod b
同余方程可以变形为
ax+by=1
因为题目保证一定有解，故
\gcd(a,b)\mid 1
可怜的 \gcd(a,b) 只能是 1 了，但是刚刚好等于 1，所以直接代换：
ax+by=\gcd(a,b)
然后就成了 exgcd 板子题了，但是注意到 x 跑出来有可能是负数，所以要加上 b 再取模。
#include <bits/stdc++.h>
using namespace std;
int a, b, x, y;
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int ans = exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * x;
return ans;
}
int main() {
cin >> a >> b;
exgcd(a, b, x, y);
x = (x + b) % b;
cout << x;
return 0;
}
显然，乘上一个数是可以正确取模的。问题转换为，如何得到一个数 a^{-1} 使 (a\bmod p)\times a^{-1}\bmod p=1，其中 p 是质数（为了防止逆元不存在）。a^{-1} 就表示 a 的逆元，也就是一个数除以 a 就等于乘上 a^{-1}。注意，a^{-1} 在不同 p 的情况下也是不同的。
同余方程求解法
显然，可以转化为同余方程
aa^{-1}\equiv 1\pmod p
来求解。
快速幂求解法
费马小定理
当 a,p 互质时，
a^{p-1}\equiv 1\pmod p
证明这里不提供，因为这毕竟是入门教程。
则有
\begin{aligned}
aa^{-1}&\equiv 1\pmod p \\
aa^{-1}&\equiv a^{p-1}\pmod p \\
a^{-1}&\equiv a^{p-2}\pmod p
\end{aligned}
\begin{aligned}
ab^{-1}+i^{-1}&\equiv0\pmod p \\
i^{-1}&\equiv -ab^{-1}\pmod p \\
i^{-1}&\equiv -\left\lfloor\dfrac pi\right\rfloor\times (p\bmod i)^{-1}\pmod p
\end{aligned}