引入： 欧几里得算法
欧几里得算法其实就是辗转相除法，用来求2个数的最大公因数。
复杂度：\(O(\log n)\)
\(code\)
int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
裴蜀定理
对于任意正整数\(a ,b\) ,一定存在非零整数\(x ,y\) ,使得
\[ax + by = \gcd (a,b) \]扩展欧几里得算法
令 \(d=\gcd(a,b)=\gcd(b ,a\) mod \(b)\)。
现有\(ax+by=bx'+(a\) mod \(b) \cdot y'=d\)，求解\(x,y\)。
\(\because\) \(bx'+(a\) mod \(b) \cdot y'=d\)
\(\therefore\) \(bx'+(a-\) \(\lfloor \frac{a}{b} \rfloor \cdot b\) \() \cdot y'=d\)
\(\therefore\) \(ay' + b \cdot (x'-\) \(\lfloor \frac{a}{b} \rfloor \cdot y'\) \()=d\)
\(\therefore\)\(\begin{cases} x = y'\\ y = x'-\lfloor \frac{a}{b} \rfloor \cdot y' \end{cases}\)
当 \(b = 0\) 时：
\[ax = \gcd (a, 0) = a \]\[x = 1 \]复杂度：\(O(\log n)\)
\(code\)
void exgcd(int a ,int b) {
if(!b) {
x = 1;
y = 0;
return;
}
exgcd(b ,a % b);
int d = x;
x = y;
y = d - a / b * y;
}
模板题
稍微转化一下
\(\because\) \(ax\) mod \(b=1\)
\(by\) mod \(b=0\)
\(\therefore\) \((ax+by)\) mod \(b=1\)
注意要求的是最小正整数解，所以处理一下\(x\)
x = (x + b) % b;