辗转相除法原理 · 欧几里得算法全解读
咱们不整虚的，就聊最硬核的数学算法——辗转相除法，也称欧几里得算法。它用最朴素的大数减小数、余数变除数的逻辑，把最大公约数问题化繁为简。
◈ 核心逻辑 · 化繁为简
① 大数除以小数
面对1000000007和23，计算器逐个减太慢。辗转相除法直接做除法：大数 ÷ 小数，得到商和余数。
② 余数变除数
若余数不为0，原来的除数变成新的被除数，余数变成新的除数。就像火锅里汤底不断替换。
③ 直到余数为零
重复相除，当余数等于0时，当前的除数就是两数的最大公约数。例如100和11，最终得到1。
◈ 典型演算 · 数字缘分
? 示例一：100 和 11
- ◆ 100 ÷ 11 = 9 ··· 余1
- ◆ 11 ÷ 1 = 11 ··· 余0
- ◆ 最终除数 1 即为公约数
? 示例二：7 和 3
- ◆ 7 ÷ 3 = 2 ··· 余1
- ◆ 3 ÷ 1 = 3 ··· 余0
- ◆ 公约数为 1
? 大数示例
- ◆ 1000000007 ÷ 23 → 余2
- ◆ 23 ÷ 2 → 余1 … 最终收敛
- ◆ 体现对数级复杂度
递归：不断缩小的游戏
辗转相除法本质上是一个递归过程。函数gcd(a,b) 不断调用自身，参数变为(b, a % b)。就像水滴石穿，数字在每一轮中急剧萎缩。例如从(1000000007,23)到(23,2)再到(2,1)，最终余数为零时返回除数。这种“大问题化小问题”的模式，是递归算法的经典体现。
程序员在脑海中玩的是“无限循环套循环”的游戏，但实际执行时栈深度仅为对数级，非常高效。
取模：偷懒的艺术
实际工程中不需要同时算出商和余数，直接使用取模运算 (%) 获得余数。例如在电商订单处理中，只需知道请求耗时毫秒数（余数），而不必计算完整商。这在处理大数据流或网络请求时特别有用。辗转相除法利用取模极大降低了计算复杂度。
当两个数非常接近时（如1000000001和1000000000），暴力算法可能更快，但绝大多数场景下欧几里得算法稳准狠。
编程思维训练
编写最大公约数函数时，你实际上在训练“化繁为简”的逻辑。把庞大项目拆解成小模块，先处理最紧急的小任务。这种由大变小的哲学，正是辗转相除法塞进代码里的智慧。它不要求你精通整个理论，只需敏锐感知余数的出现。
尤其在处理超大整数时，避免暴力相除的指数级运算，转而利用余数与除数的关系，实现对数级效率。
◈ 算法演进 · 从欧几里得到现代
欧几里得《几何原本》
最早记载辗转相除法，用于求两条线段的最大公度量。核心即为重复相减或相除。
数论形式化
数学家将算法推广到整数环，证明其总能终止于最大公约数，并用于解丢番图方程。
递归与迭代实现
成为编程入门必学算法，展示递归与迭代的转换，时间复杂度O(log min(a,b))。
乘法逆元与密码学
辗转相除法的扩展形式可求整数系数，用于RSA加密、求解模逆元，是当今安全基石。
? 深度解析：为什么余数不断缩小？
每次操作中，余数严格小于除数，因此序列严格递减。自然数的良序性保证算法必然终止。这种“不断舍弃”的过程，正是辗转相除法的美感：它不急于一口吞下庞大数字，而是逐步蚕食，直到余数消失。就像生活中面对复杂项目，先解决最棘手的部分，剩下的自然清晰。
进一步，当两个数极大时，暴力试除需要O(min(a,b))次，而欧几里得算法只需约logφ(min(a,b))步，其中φ为黄金比例。这源自斐波那契数列是最坏情况输入，例如(89,55)需要较多步骤。
另外，算法与更相减损术本质相通，但除法加速了减法过程。在二进制环境下还有stein算法（二进制gcd），避免除法运算。但辗转相除法依然是理解数论算法的第一课。
在编程竞赛中，一行代码return b==0 ? a : gcd(b, a%b); 浓缩了全部智慧。它教会我们：面对庞大问题，找到余数这个中间变量，就能把指数级难度降为对数级。这不仅是数学，更是工程哲学。