exgcd

拓展欧几里得算法

拓展欧几里得算法用于求方程 $ax+by=\gcd(a,b)$ 的一组整数解 $(x_0,y_0)$。

一旦求得一组解 $(x_0,y_0)$ ，那么它的任意整数解即为 $(x_0+kb,y_0-ka)$ 。

定义 $g=\gcd(a,b)$ ，$ax+by=\gcd(a,b)$ 的一组整数解是 $(x_0,y_0)$， 对于任意方程 $ax+by=c$ ，当 $g \mid c$ 时新方程有整数解 $(x_0\frac{c}{g},y_0\frac{c}{g})$ ，否则无整数解。

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