# 最大公约数（GCD）图解：把余数留在画面里

在原矩形里逐轮切去正方形，让余数成为下一块矩形；用统一砖网格与双向整除推导理解欧几里得算法。

原文 / Canonical: https://crazycloud.cc/learn/euclidean-algorithm
作者: crazycloudcc
首次发布: 2026-10-13
更新: 2026-10-21

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

欧几里得算法利用 gcd(a,b)=gcd(b,a%b)：每轮用较小数和余数继续，直到余数为0，最后非零除数就是最大公约数。几何上，切去整块正方形不会改变能沿两边整齐铺满的共同尺度。

## 适用条件与边界

图形只接受1–60的正整数边长，使用同一长度单位；统一砖为与矩形边平行、按行列整齐铺满的同尺寸正方形。代码接受非负安全整数且不同时为0，先取较大数为a、较小数为b。gcd(a,0)=a（a>0），但零宽矩形不拿来作铺砖证明。本课不定义gcd(0,0)；负数、小数与超出安全整数范围的输入需另行处理。

## 不变量

设d>0、b>0且a=qb+r：d同时整除a和b，当且仅当d同时整除b和r。因此每一步保留全部公因数。已切正方形与剩余矩形在原外框内无重叠、无遗漏。

## 逐步例子

1. 48×18：48=2×18+12，横向切去两块18×18正方形，留下12×18矩形。
2. 18=1×12+6，在余下区域切一块12×12，留下12×6矩形。原矩形没有旋转，数值运算始终先用长边除以短边。
3. 12=2×6+0，切去两块6×6，余数为0。因此gcd(48,18)=6，不是0。
4. 切分过程的大块尺寸不同；最终改用边长6的统一砖，原矩形能铺8列×3行。它说明最大同尺寸砖，不是任意混合大小正方形的最少块数问题。

## 为什么终止与复杂度

每轮0≤r<b，非负整数余数严格下降，最终到0；两轮内较小操作数至少减半。对正整数输入，在单位成本算术模型下，需要O(1+log min(a,b))次取模，迭代额外空间O(1)；一个输入为0时直接返回另一个。这里不计算大整数位运算成本，记录步骤和绘制网格的开销另计。

## 常见误区

- 把最后的0当答案：答案是最后非零除数；相等或整除输入可以第一轮就余0，并不一定出现正余数。
- 以为图上的大块都等于最大公约数：它们是逐轮切分的工作块，最后的统一网格才使用同一种砖。
- 只证明一个方向：d整除a和b，则整除a−qb；d整除b和r，则整除qb+r。两个方向一起保证公因数集合不变。
- 把交换数值大小当作旋转画面：原矩形位置与方向不变，每轮沿当前长边切分；画面只用同一缩放比例显示这一组输入。
- 小数也能找共同尺度吗？这里指使两个正长度都是其整数倍的最大正长度。若两长度是精确有限小数，可从十进制表示统一写成同分母分数。例如精确的111.6与46.5写成1116/10与465/10，最大共同尺度为gcd(1116,465)/10=9.3，两长度分别是它的12倍和5倍。应先用精确表示构造整数，不能保证把已存储的二进制浮点数直接乘10再取整就等价。近似测量值还须先约定误差规则，随意添加容差不会给出唯一的精确答案。本课图形与代码仍只处理上述整数范围。
- 多个正整数也能两两求吗？设g=gcd(a,b)。每轮保留公因数，最后到(g,0)，所以正整数d同时整除a、b，当且仅当d整除g。再要求d整除c，两组共同因子仍完全相同，因此gcd(a,b,c)=gcd(g,c)。例如48、18、30先得g=6，再得gcd(6,30)=6；把30换成20，结果为2。这里讨论正整数；原矩形图形仍只演示两数，不引入空输入或全零的新约定。
- 怎样用GCD约分？这里只讨论正整数分子a、分母b。令g=gcd(a,b)，分子分母分别除以g，得到(a/g)/(b/g)；共同因子g消去，相当于g/g=1，分数值不变。例如36/60同除12，得到3/5。若结果还共有整数因子d>1，则gd>g也同时整除原来的a、b，与g最大矛盾，所以已是最简。求gcd可交换输入，但约分不能交换分子分母；36/60不能写成5/3。

## 自测

24×24第一轮余数就是0，答案是什么？48×18里的18×18大块能说明最大统一砖边长18吗？

gcd(24,24)=24，取最后非零除数。48×18的18只是首轮工作块，不能沿宽48整齐铺满；最终最大统一砖边长为6。

## 删除一项：前后缀GCD合并

新增删项实验：P[0]=S[n]=0，P[i+1]=gcd(P[i],A[i])，S[i]=gcd(A[i],S[i+1])。删除i后结果gcd(P[i],S[i+1])，不是相减。数组限定2–8个1–60正整数，不会调用gcd(0,0)。12、18、25、30删25后为gcd(6,30)=6。两遍预处理与全部候选合并总计O(n(1+log V))时间、O(n)空间（单位成本取模）。

原题ABC125C允许替换一项；替换成其余数的GCD可以达到相同最优值。本实验只展示删项合并。GCD没有前缀和相减的逆操作；数组改值后必须重建两侧表。

## 延伸学习

欧几里得算法让余数严格减小；二分答案让搜索区间缩小。两者都需说明为何终止，但保留的性质不同。

[对比：二分答案的单调区间](https://crazycloud.cc/learn/binary-search-on-answer)

## 参考资料

- [AtCoder ABC125C：GCD on Blackboard（2019-04-27）](https://atcoder.jp/contests/abc125/tasks/abc125_c)
- [ABC125官方题解：前后缀GCD](https://img.atcoder.jp/abc125/editorial.pdf)
- [MIT OCW 6.1200：整除、欧几里得算法与矩形（2024-03-05）](https://www.ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/1nbxrnTlb8xzIffjCnaTesZ8bEgKO592i_transcript.pdf)
- [Python 官方教程：二进制浮点表示与十进制近似](https://docs.python.org/3/tutorial/floatingpoint.html)

[返回图解实验室](https://crazycloud.cc/learn)