不定方程-扩展欧几里得算法

用来求$ax+by=gcd(a,b)$的一组整数解

扩展欧几里得算法

当$b=0$时，显然$x=1,y=0$是一组解 当$b\neq0$时， $\begin{aligned} \operatorname{gcd}(a, b) & =a x+b y \\ \operatorname{gcd}(b, a \% b) & =b x_{1}+(a \% b) y_{1} \\ & =b x_{1}+\left(a-\left\lfloor\frac{a}{b}\right\rfloor \times b\right) y_{1} \\ & =a y_{1}+b\left(x_{1}-\frac{a}{b} y_{1}\right) \end{aligned}$ 所以:$x=y_{1}, y=x_{1}-\frac{a}{b} y_{1}$ 通解： $\left\{\begin{array}{l} x=x_{0}+\frac{b}{\operatorname{gcd}(a, b)} * k \\ y=y_{0}-\frac{a}{\operatorname{gcd}(a, b)} * k \end{array}\right. ( 考虑 a x+b y=0 构造 )$

int exgcd(int a,int b,int &x,int &y){
    if (b==0){
        x=1,y=0;
        return a;
    }
    int x1,y1,d;
    d= exgcd(b,a%b,x1,y1);
    x=y1,y=x1-a/b*y1;
    return d;
}

求不定方程$ax+by=c$的一组整数解： 如果$gcd(a,b)|c$,一定有整数解，否则没有 的一组解，在乘以$\frac{c}{gcd(a,b)}$，即可得到原方程的特解。