扩展欧几里得算法

算法

阅读此篇前可先阅读欧几里得算法。

给定 \(a,b,s\)，求 \(ax+by=s\) 的任意一组解。

证明:

由裴蜀定理得：二元一次方程 \(ax+by=c\) 的有解条件是 \(\gcd(a,b) \mid c\)。

由欧几里得算法得知 \(\gcd(a,b)=\gcd(b,a\mod b)\)

假设我们求出了 \(\gcd(b,a\mod b)\) 的两个解 \((x'，y')\)。

则可以得到：\(ax+by=bx'+(a\mod b)y'\)。

而我们又知道 \(a\mod b=a-b\times\lfloor{\frac{a}{b}}\rfloor\)。

则 \(ax+by=bx'+(a-b\times\lfloor{\frac{a}{b}}\rfloor)y'\)

\(ax+by=ay'+b(x'-\lfloor{\frac{a}{b}}\rfloor y')\)

所以有一组解：\(x=y',y=x'-\lfloor{\frac{a}{b}}\rfloor y'\)。

然后根据欧几里得算法一步一步往上推即可。

初始值要设为：\(x=1,y=0\)。

void exgcd(int a,int b){
    if(!b){x=1,y=0;return ;}
    exgcd(b,a%b);
    int t=x;
    x=y,y=t-a/b*y;
}