最大公约数

定义

若 c ∣ a 且 c ∣ b，那么称 c 为 a 和 b 的公约数。

在 a 与 b 的所有公约数中，最大的那一个称为最大公约数，记为 gcd (a, b)，在不混淆的情况下亦可记为 (a, b)。

性质

• gcd (a, gcd (b, c)) = gcd (gcd (a, b), c)​。

• 假设维护一个集合的 gcd  = x，设新增一个数后新的 gcd  = x′，则有 x′ ≤ x，且变化次数最多 log n 次。

• 设 a = ∏p_i^α_i, b = ∏p_i^β_i (p_i ∈ ℙ) 那么 gcd (a, b) = ∏p_i^{min {α_i, β_i}} 其中认为不存在的质因数 p_i 的指数为 0。

辗转相除法

定理

gcd (a, b) = gcd (b, a mod  b)

证明：

不妨令 a > b​。

设 a = b ⋅ k + r，r < b（r = a mod  b​）。

设 g = gcd (a, b)，且 a = n ⋅ g，b = m ⋅ g。

那么 r = a − b ⋅ k = (n − m ⋅ k)g，故 g ∣ gcd (b, r)。

接下来证明 g = gcd (b, r)，即证明 m ⊥ n − m ⋅ k​。

---

考虑使用 反证法。

若存在 ，那么 d ∣ n，于是 d ⋅ g ∣ n ⋅ gand d ⋅ g ∣ m ⋅ g，这与 g = gcd (a, b) 相悖，故 m ⊥ n − m ⋅ k，所以 g = gcd (b, r)。

时间复杂度

最差时间复杂度为 O(log max {a, b})​，且当 a, b 为斐波那契数列中相邻的两个数时复杂度最大。

证明：

• 当 a < b 时，gcd (a, b) = gcd (b, a)。
• 当 a ≥ b 时，此时 gcd (a, b) = gcd (b, a mod  b)，而 ，所以这一情况最多出现 O(log a) 次。

a < b 交换后就会发生 a ≥ b 的情况，故 a < b 的次数 不多于 a ≥ b 的次数。

故时间复杂度为 O(log max {a, b})。

代码实现

template <typename _Tp>
_Tp gcd(_Tp a, _Tp b) {
  for (_Tp tmp = a; b; tmp = a) {
    a = b;
    b = tmp % b;
  }
  return a;
}

更相减损法