『算法-ACM 竞赛-数学-数论』欧几里得定理和拓展欧几里得定理

数学–数论–欧几里得定理和拓展欧几里得定理

欧几里得定理:

gcd(a, b) = gcd(b, a%b)

证明：
我们首先约定：m = gcd(a,b) , n = gcd(b, q) , a = bp +q。（这里的 gcd 含义跟上面一样，q 的含义跟后面式子同）
1. m 是 a,b 的最大公约数，那么 m 整除 a,b
q = a - bp
m 也可以整除 q
=>m 就是 b 和 q 的公约数
=>n 是 b,q 的最大公约数
=>n >=m

2. =>n 是 q,b 的最大公约数，那么 n 整除 q,b
=>a = b*p + q
=>n 也可以整除 a
=>n 就是 b 和 a 的公约数
=>m 是 b,a 的最大公约数
=>m >= n

3.q=a%b
综上所述，那么我们可以得出 n = m,及 gcd(a, b) = gcd(b ,a%b)

实现：

int gcd(a, b)
{
    if(b == 0)
        return a;
    return gcd(b, a%b);
}

三目运算符优化：

int gcd(a, b)
{
    return b == 0?a:gcd(b, a%b);
}

拓展欧几里得定理：