ki-pi1. 最大公约数问题引入
作为一名长期从事算法教学的老师，我发现最大公约数（GCD）这个概念对于初学者来说既熟悉又陌生。熟悉是因为小学数学就接触过，陌生是因为很少有人真正理解其背后的数学原理和高效算法。
让我们从一个生活场景开始：假设班级里有12个苹果和18个香蕉，要平均分给尽可能多的小组，每个小组得到的苹果和香蕉数量必须相同。经过尝试我们会发现：
- 分给2组：每组6苹果9香蕉
- 分给3组：每组4苹果6香蕉
- 分给6组：每组2苹果3香蕉
这个问题的本质就是在寻找12和18的最大公约数。当数字较小时，我们可以用枚举法轻松解决。但当面对像(1872, 1536)这样的大数时，枚举法就显得力不从心了。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 欧几里得算法原理剖析
2.1 几何直观理解
欧几里得在《几何原本》中提出的算法，可以用一个形象的"铺地砖"问题来理解：
想象我们要用相同大小的正方形地砖铺满一个18×12的长方形。最大的地砖边长是多少？
- 先用12×12的地砖铺：会剩下6×12的长条
- 再用6×6的地砖铺剩下的长条：正好铺满
- 因此最大地砖边长是6
这个铺砖过程揭示了GCD的核心性质：GCD(a,b) = GCD(b, a mod b)。这种"以大化小"的思想，正是算法高效的关键。
2.2 数学证明
严谨的数学证明如下：
设a = bq + r，其中0 ≤ r < b
如果d是a和b的公约数，那么：
d|a且d|b ⇒ d|(a - bq) ⇒ d|r
反之，如果d是b和r的公约数：
d|b且d|r ⇒ d|(bq + r) ⇒ d|a
因此a和b的公约数集合等于b和r的公约数集合，GCD自然也相同。
3. C++实现详解
3.1 基础递归版本
cpp复制int gcd_recursive(int a, int b) {
if (b == 0)
return a;
return gcd_recursive(b, a % b);
}
这个版本直接体现了算法的数学定义：
- 基准情况：当b为0时，a就是GCD
- 递归情况：计算GCD(b, a mod b)
时间复杂度：O(log min(a,b))，因为每次递归调用至少将问题规模减半。