最大公约数（GCD）

Published on	7/29/2025
Created on	10/18/2021

GCD abbr. of Greatest Common Divisor（最大公约数）另一个名称是 Highest Common Factor

链接

定义

\gcd(a,b)=max\{d\ |\ a=de\ \wedge\ b=df,\quad d,e,f\in\mathbb{Z}\}\quad(a,b\in\mathbb{Z})

性质

交换律： $\gcd(a,b)=\gcd(a,b)$
$\gcd(-a,b)=\gcd(a,b)$
$\gcd(a,a)=\gcd(a,0)=|a|$
$\gcd(a,b)=\gcd(b,a-b)$ （更相减损法）
$\gcd(a,b)=\gcd(b,a\%b)$ （辗转相除法）
$\gcd(a,b)\times\mathrm{lcm}(a,b)=ab$
在坐标里，将点 $(0, 0)$ 和 $(a, b)$ 连起来，通过整数坐标的点的数目（除 $(0, 0)$ 之外）就是 $\gcd(a, b)$

辗转相除法

C/C++ 非递归版本

int gcd(int m, int n) {
 int t = 1;
 while (t != 0) {
  t = m % n;
  m = n;
  n = t;
 }
 return m;
}

C/C++ 递归版本

template<typename T>
T gcd(T a,T b){
 return b?gcd(b,a%b):a;
}

时间复杂度： $\mathrm{O}(\log n)$ 参考