描述

欧几里德算法
别名：辗转相除法
用途：计算两个正整数a,b的最大公约数

欧几里德拓展算法
扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足等式： ax+by=gcd(a,b)=d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。

代码

C++ 欧几里德
LL gcd (LL a, LL b) {
    return b ? gcd(b, a%b) : b;
}

C++ 拓展欧几里德
void exgcd (LL a, LL b, LL& d, LL& x, LL& y) {
    if (b) {
        d = a;
        x = 1;
        y = 0;
    } else {
        exgcd(b, a%b, d, y, x);
        y -= (a/b)*x;
    }
}

简单推导

对于ax+by=c，用拓展欧几里德算法求一对解，|x|+|y|最小的值。当c=k?gcd(a,b)有整数解，当c!=gcd(a,b)时无解。

• g=gcd(a,b),设x0,y0为ax+by=g的一组解
• 那么ax+by=c的一组解即为x0?c/g,y0?c/g
• 若xi=x0?c/g为整数解，那么有c=k?g

通解

• x=x0+k?b′(b′=b/gcd(a,b)
• y=y0+k?a′(a′=a/gcd(a,b)