两根绳子，三下除法，就能算出最大公约数——辗转相除法到底妙在哪？
你有没有遇到过这种情况：手里有48颗糖，朋友有18颗糖，想把它们分成几堆，每堆数量一样、必须是整数、而且一颗都不能剩。你可能会从1开始试着除，试到18，发现最大能分成6颗一堆。可如果数字变成几百万呢？你还想一个个试吗？
两千多年前的欧几里得早就想明白了一个道理：与其去“找”公约数，不如把两个数“量”出来。就像用一根长绳量一根短绳，量完剩下的余头，再用短绳去量余头……最后那根能正好量完上一根的绳子，就是答案。
先别急着写代码，理解“为什么能这么做”
给你两根绳子，一根48厘米，一根18厘米。你想找一根最长的小绳，能同时量完这两根。
48里最多有两个18，剩下12厘米。现在问题变成了：18和12的公约数，是不是和48和18的公约数完全一样？
答案是肯定的。因为48 = 18×2 + 12，所以任何能同时整除48和18的数，一定能整除12；反过来，任何能同时整除18和12的数，也一定能整除48。公约数集合没变，最大公约数自然也没变。
于是我们把求 gcd(48, 18) 转化成了求 gcd(18, 12)，数字变小了，问题却没变。继续：
- 18 = 12×1 + 6
- 12 = 6×2 + 0
余数为0，最后那个非零除数6就是答案。整个过程不过三次除法。
这也是辗转相除法最迷人的地方：每做一次除法，问题规模就急剧缩小。余数一定小于除数，而更关键的是，余数通常连除数的一半都不到（想想为什么？因为如果余数超过一半，商就可以再加1了）。所以对于百万级别的数，最多也就二十来步。
代码就几行，但别轻视它
递归写法最直观：
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
循环写法更省栈空间：
int gcd(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
有个新手经常踩的坑：总想先交换两数，保证a >= b。其实完全没必要。如果a < b，第一次 a % b 的结果就是a本身，然后赋值后自动交换了角色。多写那个 swap 不算错，但这种“多余的谨慎”往往来自没有真正理解算法本身。
真正要注意的是输入不能两个都是0，否则第一次取模就崩了。一般题目里都会保证正整数，但如果自己做测试，记得加个判断。
一道“素数个数”题，居然也能和它扯上关系？
有个题目问你：1到N之间有多少个素数？N最大能到一亿。你可能会想：这跟最大公约数有什么关系？
直接判断每个数是不是素数，复杂度是O(N√N)，一亿根本跑不动。但你发现没有——求素数个数，本质上是在做排除法。而排除的核心，是“用素数筛掉倍数”。怎么快速判断某个数是否已经被筛掉？依然离不开整除操作。虽然这题真正的高效解法是欧拉筛或埃氏筛，但在实现筛法时，你同样需要频繁用到“整除”和“余数”的概念。
辗转相除法教你的是：余数不是垃圾，它是缩小问题规模的钥匙。在编程竞赛里，很多优化都源于对余数的巧妙利用。比如判断一个数能否被某个素数整除，本质就是看 n % p == 0。理解了余数的意义，再看“筛法优化”“哈希取模”“循环节”这些问题，你会比别人多一层敏感。
那道最大比例的题目就更是直接了。给你几个数，它们构成一个等比数列，但中间有缺失，让你反推最大的公比。你会得到一堆分数，比如4/3、16/9、8/3……怎么找到它们共同的最大“比例公约数”？普通除法办不到，因为你要找的不是一个数能同时整除它们，而是一个分数能同时“整除”这些分数。
怎么办？把分子分别求最大公约数，分母分别求最小公倍数。最终得到的分数就是这些比例的最大公比。你再仔细品品——这里求分子最大公约数用的，还是辗转相除法。同一个算法，换了一层皮，就解决了分数比例问题。
聊聊这个算法的“底层气质”
很多人学算法只记代码，不看思路，遇到变体就懵了。辗转相除法的变体很多：
- 求最大公约数可以扩展到多个数：两两求，最终合并。
- 求最小公倍数只需要
a / gcd(a,b) * b，注意先除后乘防止溢出。 - 扩展欧几里得算法能解
a*x + b*y = gcd(a,b)，后面的逆元、RSA加密全都要用到它。
说白了，辗转相除法之所以重要，不是因为代码短，而是它展示了一种思维范式：把一个看似复杂的问题，通过“取余”操作快速降维，直到问题自然显形。
你以后会遇到二分、快速幂、gcd的递归写法……这些算法的核心都带着同样的味道——每一步都在缩小问题，但答案始终不变。你只要抓住了“不变性”，代码怎么写都不会错。
所以下次你看到 while(b) swap(a%=b, b); 这种一行代码时，别只觉得帅。它背后是一个用绳子量了两千年的朴素智慧。如果你真的理解了，那以后不管数字多大，也不过是几行除法的事。
关于作者
我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。
这些年累计帮助 多名 学生通过编程特长升入自己心仪的目标学校。
如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）