最大公约数

定义

若 $c\mid a$ 且 $c\mid 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'\le x$，且变化次数最多 $\log n$ 次。

• 设

  $$ a=\prod{p_i^{\alpha_i}},b=\prod{p_i^{\beta_i}}\,(p_i\in\mathbb{P}) $$

  那么

  $$ \gcd(a,b)=\prod{p_i^{\min\{\alpha_i,\beta_i\}}} $$

  其中认为不存在的质因数 $p_i$ 的指数为 $0$。

辗转相除法

定理

$$ \gcd(a,b)=\gcd(b,a\bmod b) $$

证明：

不妨令 $a>b$​。

设 $a=b\cdot k+r$，$r

设 $g=\gcd(a,b)$，且 $a=n\cdot g$，$b=m\cdot g$。

那么 $r=a-b\cdot k=(n-m\cdot k)g$，故 $g\mid\gcd(b,r)$。

接下来证明 $g=\gcd(b,r)$，即证明 $m\perp n-m\cdot k$​。

---

考虑使用 反证法。

若存在 $d>1\space s.t.\space d\mid m\operatorname{and} d\mid n-m\cdot k$，那么 $d\mid n$，于是 $d\cdot g\mid n\cdot g \operatorname{and} d\cdot g\mid m\cdot g$，这与 $g=\gcd(a,b)$ 相悖，故 $m\perp n-m\cdot k$，所以 $g=\gcd(b,r)$。

时间复杂度

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

证明：

• 当 $a
• 当 $a\ge b$ 时，此时 $\gcd(a,b)=\gcd(b,a\bmod b)$，而 $a\bmod b\le\dfrac{a}{2}$，所以这一情况最多出现 $O(\log a)$ 次。

$a不多于 $a\ge b$ 的次数。

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

代码实现

1
2
3
4
5
6
7
8

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

更相减损法