考虑如何求解以下方程 ：
\[ ax\equiv 1\pmod b \]显然可以转化为 ：
\[ ax+by=1 \]有裴蜀定理 :
对于不定方程 \(ax+by=c\)，其有解当且仅当 \(\gcd(a,b)|c\)。
可以发现上述方程有解当且仅当 \(\gcd(a,b)=1\)，故可以转化为 ：
\[ ax+by=\gcd(a,b) \]观察到当 \(b=0\) 时方程有特解 \(x=1,y=0\)，于是考虑如何递归求解。
因为上式中有辗转相除的影子，于是尝试构造 ：
\[ bx'+(a~mod~b)y'=\gcd(b,a~mod~b) \]有 \(a\ mod\ b=a-\lfloor\frac{a}{b}\rfloor b\)，化简可得 ：
\[ ay'+b\left(x'-\lfloor\frac{a}{b}\rfloor y'\right)=\gcd(b,a~mod~b)= \gcd(a,b) \]于是我们发现，如果求出了方程 \(bx'+(a\ mod\ b)y'=\gcd(b,a\ mod\ b)\) 的解 \(x'\) 和 \(y'\)，那么方程 \(ax+by=\gcd(a,b)\) 的解为 ：
\[ x=y',y=x'-\lfloor\frac{a}{b}\rfloor y' \]于是这样就可以在辗转相除的过程中递归求解了，时间复杂度 \(\Theta(\log n)\)。
#include<bits/stdc++.h>
using namespace std;
int a, b, x, y;
void Exgcd (int a, int b) {
if (b == 0) {
x = 1 , y = 0;
return;
}
Exgcd(b, a % b);
int tmp = x;
x = y, y = tmp - a / b * y;
}
int main () {
cin >> a >> b;
Exgcd(a, b);
cout << (x + b) % b << endl;
return 0;
}
