欧几里得算法
定理 $gcd(a,b)=gcd(b,a \bmod b)$
证明：
设 $p$ = $\lfloor a/b \rfloor$，则 $a = b \cdot p + m, a \bmod b = m$。
因为 $a$ 和 $b$ 是 $gcd (a,b)$ 的倍数，所以 $b \cdot p, b \cdot p + m$ 是 $gcd (a,b)$ 的倍数，因此 $m$ 是 $gcd (a,b)$ 的倍数。所以 $gcd (a,b)$ 是 $m, b$ 的因数。
又因为 $gcd (b, a \bmod b) = gcd (b, m)$，即 $gcd (b, a \bmod b)$ 是 $b, m$ 的最大公因数，所以 $gcd (a,b)$ 是 $gcd (b, a \bmod b)$ 的因数。
同理，$b$ 和 $m$ 是 $gcd (b,m)$ 的倍数，所以 $b \cdot p + m$ 即 $a$ 是 $gcd (b, m)$ 的倍数。
所以 $gcd (b,m)$ 是 $a$ 与 $b$ 的因数。
又因为 $gcd (a,b)$ 是 $a,b$ 即 $b \cdot p + m, b$ 的最大公因数，所以 $gcd (b,m)$ 是 $gcd (a,b)$ 的因数。
所以 $gcd (a,b) = gcd (b, a \bmod b)$。
于是我们可以快速求出 $gcd (a,b)$。
int gcd (int a, int b) {
if (b == 0) return a;//临界条件b=0
return gcd (b, a % b);
}拓展欧几里得算法
求一组解
有时候，我们遇到这样一类问题，求方程 $a \cdot x + b \cdot y = c$ 的解，此时我们可以使用拓展欧几里得算法。
定理：设 $x,y$ 为正整数，则关于 $x, y$ 的方程 $a \cdot x + b \cdot y = c$ 有整数解当且仅当 $c$ 是 $gcd (a, b)$ 的倍数。
于是可以排掉无解的情况，并得到 $c$ 是 $gcd (a,b)$ 的性质。
随后进行求解，具体而言，是在辗转相除的过程中求出解，也可以说，用 $a_0 = b, b_0 = a \bmod b$ 时 $a_{0} \cdot x_0 + b_{0} \cdot y_0 = c$ 的解 $x_0, y_0$ 推出 $a \cdot x + b \cdot y = c$ 的解 $x, y$。
那么如何用 $a_{0} \cdot x_0 + b_{0} \cdot y_0 = c$ 的解推出 $a \cdot x + b \cdot y = c$ 的解呢。
将 $a_0 = b, b_0 = a \bmod b$ 带入得，$bx_0 + (a \bmod b) \cdot y_0 = c$。
设 $p$ = $\lfloor a/b \rfloor$。
$a \bmod b = a - p \cdot b$。
所以 $bx_0 + (a - pb) \cdot y_0 = c$。
展开得 $a \cdot y_0 + b \cdot (x_0 - p \cdot y_0) = c$， 所以当 $x = y_0, y = x_0 - p \cdot y_0$ 时，$a \cdot x + b \cdot y = c$， 此时 $x, y$ 是 $a \cdot x + b \cdot y = c$ 的一组解。
$b = 0$ 时， 令 $x = c/a, y= 0$ 得到一组解 $x, y$，最后从 $b=0$ 的情况一步步推算得到最终的一组解。
void exgcd (int a, int b, int &x, int &y, int c) {
if (b == 0) {
x = c / a;
y = 0;
return;
}
exgcd (b, a % b, x, y, c);
int x0 = x, y0 = y;
x = y0;
y = x0 - (a / b) * y0;
}调解
显然方程 $a \cdot x + b \cdot y = c$ 不止一组解，所以我们考虑调解，得到具体题目要求的解（一般是一定范围内的最小/大解）。
结论
$x_k = k \cdot b / gcd (a, b), y_k = k \cdot a / gcd (a, b) $。
于是我们可以根据题目范围求出特殊解。