欧几里得算法与扩展欧几里得算法

欧几里得算法，即人教版高中数学必修三上的辗转相除法

用于求两个整数的最大公因数(即gcd(a,b))
注:a b的最小公倍数等于$$\frac {ab}{\gcd \left(a,b\right)}$$

int gcd(int a, int b) {
    //边界b==0 此时a就是结果
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

扩展欧几里得算法:在求最大公约数的同时求出方程$$ax+by=gcd(a,b)$$的一组整数解，使|x|+|y|最小

//a b 方程中的a b 
//gcd 用来存放gcd(a,b)
//x y 用来存放解
void exgcd(int a, int b, int & gcd, int& x, int& y) {
    //边界b==0 此时a就是结果
    if (b == 0) {
        x = 1;
        y = 0;
        gcd = a;
    } else {
        exgcd(b, a % b, gcd, y, x);
        y -= (a / b) * x;

    }
}

求出$$ax+by=gcd(a,b)$$的解之后,如果$$c$$可以整除$$gcd(a,b)$$ 就说明方程$$ax+by=c$$存在整数解$$x_0,y_0$$，而且这组解为$$x_1=x_0*c/gcd(a,b),y_1=y_0*c/gcd(a,b)$$

然后，如果$$x_1,y_1$$是方程$$ax+by=c$$的解,则$$x_1+k*a/gcd(a,b),y_1-k*b/gcd(a,b)$$都是方程$$ax+by=c$$的解