【数学】【模板】欧几里得算法

欧几里得算法

思想

证明 \(\gcd(a, b) = \gcd(b, a \bmod b)\)：

首先，如果有 \(d | a\)，\(d | b\)，那么 \(d | ax + by\)。

然后，\(a \bmod b = a - \left\lfloor\dfrac{a}{b}\right\rfloor b\)。

假设 \(p = \gcd(a, b)\)，那么 \(p | a\)，\(p | b\)，所以 \(p | a\cdot 1 - b \cdot \left\lfloor\dfrac{a}{b}\right\rfloor\)，而 \(a\cdot 1 - b \cdot \left\lfloor\dfrac{a}{b}\right\rfloor = a\bmod b\)，所以 \(p\) 既能整除 \(a, b\)，也能整除 \(a \bmod b\)，所以 \(\gcd(a, b) = \gcd(b, a \bmod b)\)。

代码

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