扩展欧几里得算法
常用来计算不定方程 \(ax+by=\gcd(a,b)\) 的一组特解，采用递归的计算流程
\[\gcd(a,b)=ax+by\\
\]
根据欧几里得定理可知
\[\gcd(a,b)=\gcd(b,a\ \mathrm{ mod}\ b)\\
\gcd(b,a\ \mathrm{ mod}\ b)=bx_1+(a-\lfloor\frac{a}{b}\rfloor\times b)y_1
\]
拆开括号移项后得到
\[\begin{align}
\gcd(a,b)&=ax+by\\
\gcd(b,a\ \mathrm{ mod}\ b)&=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1)\\
\Rightarrow x=y_1&,y=x_1-\lfloor\frac{a}{b}\rfloor y_1\end{align}
\]
当递归计算 \(\gcd(a,b)\) 中的 \(b = 0\) 时，\(ax=\gcd(a,0)=a\) ，此时应当返回 \(x=1,y=0\)；逐层向上回代计算
最终求得特解 \(x_0,y_0\) ，然后考虑通解的构造
\[\left\{
\begin{align}
x=x_0+\frac{b}{\gcd(a,b)}\times k\\
y=y_0-\frac{a}{\gcd(a,b)}\times k\\
\end{align}
\right.
\]
这样构造的原因是可以满足
\[a\left(x_0+\frac{b}{\gcd(a,b)}\times k\right) + b\left(y_0-\frac{a}{\gcd(a,b)}\times k\right)=ax_0+by_0=\gcd(a,b)
\]
LL exgcd(LL a, LL b, LL &x, LL &y){if (b == 0){x = 1, y = 0;return 1;}LL x1, y1, d;d = exgcd(b, a % b, x1, y1);//递归计算下一层x = y1, y = x1 - a / b * y1;//回代计算return d;//返回当前gcd(a, b)
}
不定方程
根据裴蜀定理，可以证明方程 \(ax+by=c\) 存在正整数解当且仅当 $c\equiv 0(\mathrm{mod}\ \gcd(a,b)) $
在计算不定方程的过程中，可以先计算出方程 \(ax+by=\gcd(a,b)\) 的某个特解
然后将特解 \(x_0,y_0\) 乘上 \(\frac{c}{\gcd(a,b)}\) 得到 \(ax+by=c\) 的特解 \(x_t,y_t\) ，构造通解有：
\[\left\{
\begin{align}
x=x_t+\frac{b}{\gcd(a,b)}\times k\\
y=y_t-\frac{a}{\gcd(a,b)}\times k\\
\end{align}
\right.
\]
同余方程
形如 \(ax\equiv b(\mathrm{mod}\ m)\) 的方程为同余方程，可以利用扩展欧几里得算法求解
\[ax\equiv b\mod m \iff ax=(-my) + b\\
\]
得到 \(ax+my=b\) ，这个不定方程利用扩展欧几里得算法求解后可以得到一组特解（\(b\) 应当被 \(\gcd(a,m)\) 整除）
乘法逆元
当 \(a,m\) 互质时，对于同余方程 \(ax\equiv1(\mathrm{mod\ m})\) 求 \(a\) 的乘法逆元 \(x\)
同样转化为 \(ax+my=1\) ，然后求解 \(ax+my=\gcd(a,m)\) 的特解 \(x\)
最终的逆元应该被表示为 \(x\ \mathrm{mod}\ m\)
LL exgcd(LL a, LL b, LL &x, LL &y){if (b == 0){x = 1, y = 0;return 1;}LL x1, y1, d;d = exgcd(b, a % b, x1, y1);x = y1, y = x1 - a / b * y1;return d;
}LL a, b, x, y;
cin >> a >> b;
LL g = exgcd(a, b, x, y);
cout << (x % b + b) % b;