辗转相除法
入门辗转相除法（欧几里得算法）是求 GCD 的最经典方法。
// 算法讲解
辗转相除法
观察欧几里得算法通过取模递归求 GCD 的过程。
待机
速度 中
待机 ⌨1int gcd(int a, int b) {
2 while (b) {
3 int t = b;
4 b = a % b;
5 a = t;
6 }
7 return a;
8}
9
10int extGcd(int a, int b, int& x, int& y) {
11 if (b == 0) { x = 1; y = 0; return a; }
12 int x1, y1;
13 int g = extGcd(b, a % b, x1, y1);
14 x = y1;
15 y = x1 - (a / b) * y1;
16 return g;
17}
复杂度分析
时间 O(log min(a,b))
空间 O(log min(a,b))
最优 O(1)
最坏 O(log min(a,b))
算法讲解
辗转相除法基于 gcd(a, b) = gcd(b, a mod b) 这一核心性质。
当 b=0 时，gcd(a, 0)=a 就是递归终止条件。
它的正确性来自整除的性质：a = bq + r，任何同时整除 a 和 b 的数也整除 r，反之亦然。
扩展欧几里得算法还可以求出 ax + by = gcd(a,b) 的一组整数解，是求解线性同余方程的基础。