最大公约数（Great Common Divisor）
假设对于非负整数，$a$ , $b$ ，求它们的最大公约数 $\text{gcd}(a, b)$ ，以下简写作 $g$ 。
数学上，最大公约数只有对两个非零整数才有意义，但是一般从实现的方面，规定：
- $\text{gcd}(0, b) = a$ , $\text{gcd}(a, 0) = a$
- $\text{gcd}(0, 0) = 0$
辗转相减
也是原始的欧几里得（Euclidean）算法。
根据定义有：
\[\begin{array}{l} a &= ng \\ b &= mg \end{array}\]$\text{n}$ , $\text{m}$ 互质，对于 $a \neq b$ 的情况，不失一般性地假设 $a > b$ ，也就是 $n > m$ ，这样的话，$a-b = (n - m) g$ ，$b=mg$ 也有公约数 $g$1 。
这样取 $a=\text{max}(a-b, b)$ , $b=\text{min}(a-b,b)$ ，也就是如果 $n-m > m$ 仍然成立就继续减，否则就是交换 $a$ , $b$ 的位置，在这个过程中 $n > \text{max}(n-m,m) = \text{max}(n, m) > \text{max}(n-m, m)$ 系数的上限不断下降，直到 $a=b$ 。
此时也有 $a=g$ ，$b=g$，此时就得出了最大公约数 $g$ 。
def gcd(a, b):
if a < b: a, b = b, a
if b != 0:
while a != b:
if a > b: a, b = b, a
a -= b
return a
辗转取余
辗转取余是原始欧几里得算法的变种。
回过去观察相减的过程，如果 $a=qb+r, (q \geqslant 0,\ r < b)$ , 每次 $a-b$ 就是 $q-1$ ，直到 $q=0$ ，因为 $a=r<b$ 然后就交换 $a,b$ 位置，可以通过取余的操作一步到位的完成，$a \% b$ 直接得到 $r$ , 然后和 $b$ ，即使开始时 $a < b$ , 也不影响 $a\%b$ 的结果。
def gcd(a, b):
while b > 0:
a, b = n, a % b
return a
从实践上看，不考虑特殊指令优化的情况下，这种方法的效率是最佳的。
拓展 GCD
拓展 gcd 是在求解最大公约数的同时求解出一组解 $(x,y)$ 使得 $ax+by = \text{gcd}(a,b)$ 2
递归
通过递归的方式(辗转取余)求解是最容易理解的实现：
\[\begin{array}{l} g &= a_0x_0 + b_0y_0 \\ &= a_1x_1+b_1y_1 \\ &= b_0x_1 + (a_0-\lfloor \frac{a_0}{b_0} \rfloor b_0) y_1\\ &= a_0y_1 + b_0(x_1 - \lfloor \frac{a_0}{b_0} \rfloor y1) \end{array}\]按照对应项系数相等的方法，得到一组解：
\[\begin{array}{l} x_0 &= y_1 \\ y_0 &= x_1-\lfloor \frac{a_0}{b_0} \rfloor b_0y_1\\ &= x_1-\lfloor \frac{a_0}{b_0} \rfloor b_0x_0 \end{array}\]最后推到 $a_n=b, b_n=0$ 时，$g = b = 0x + 1b$ , 也就是取 $x_n = 0, y_n=1$ ，
def ext_gcd(a, b):
if b == 0:
return (a, 0, 1)
(g, x1, y1) = ext_gcd(b, a % b)
x = y1
y = x1 - (a/b) * x
return (g, x, y)
展开
展开版本来源于 cp-algorithms ，你说我完全理解，我说我完全不理解！
def ext_gcd(a, b):
x, y = 1, 0
x1, y1 = 0, 1
a1, b1 = a,b
while b1 > 0:
q = a1 / b1
x, x1 = x1, x - q * x1
y, y1 = y1, y -q * y1
a1, b1 = b1, a1 - q * b1
return a1, x, y
模乘逆元
计算正整数 $a$ 关于 $m$ 的模乘逆元 $x$ ，也即 $a\cdot x \equiv 1 \mod m$
利用拓展公约数算法，let (_, x, y) = ext_gcd(a, m) ，这样有 $a\cdot x + m\cdot y = 1$ ，两边取余得到 $a\cdot x + 0 \equiv 1 \pmod m$ ，也就是拓展公约数可以直接求出模乘逆元。
注解
