算法 / 整除与几何
最大公约数 Euclidean Algorithm
把余数留在画面里
切去整块正方形，留下更小的矩形。尺寸在变，共同的整除尺度不变。
轮次切换只为观察切分，所有尺寸始终是整数。输入改变时重新开始并重新适配画面，不能比较不同输入的像素长度。减动画偏好下禁用播放，单步仍可使用。网格提前显示会揭示答案。
为什么换成余数，共同尺度不变？
若 d 同时整除 a 和 b，就整除 r=a−qb；反过来，若 d 整除 b 和 r，就整除 a=qb+r。两边的公因数集合相同，最大值也相同。
// 本课：非负安全整数，不允许同时为0
let a = Math.max(width, height);
let b = Math.min(width, height);
while (b !== 0) {
const r = a % b;
a = b;
b = r;
}
return a;
// 本轮：a=48, b=18, r=12
// 下一对：(18, 12)进阶实验：删去一项，怎样不从头再算？
把数组画成一排长度条。先从两边分别合并公因数，再让待删除项退出，连接留下的左右区间。原来的矩形切分实验不变，这里只处理2–8个1–60的正整数。
前缀扫描：已处理[0,0)，P[0]=0。下一项并入左侧集合。
P[0] = 0
for i = 0 .. n-1:
P[i+1] = gcd(P[i], A[i])
// 已完成 0 项；P[0] = 0为什么成立？留下的每个数恰好属于左段或右段。一个正整数d整除所有留下的数，当且仅当它同时整除两段各自的GCD。因此取gcd(P[i], S[i+1])，不是相减。
默认例子12、18、25、30：删去下标2的25，左段GCD为6，右段GCD为30，合并为6。删首项或末项时有一侧为空，以0作该段的合并单位；n≥2且元素为正，所以不会调用gcd(0,0)。原两数算法的输入约定不变。
预处理做两遍扫描，每个候选位置再合并一次：若最大值为V，单位成本取模模型下总计O(n(1+log V))时间、O(n)空间；不是每次删除都复制数组重算。若求最优位置，比较所有候选结果即可。固定数组的前后缀表不能在修改元素后直接复用，界面改值会重新开始。
与前缀和对比：和能通过相减去掉左段，GCD没有这种逆操作。这里保存左右两份摘要。真实练习见ABC125C（2019-04-27）：原题是替换一项；把该项改成其余数的GCD即可达到同一最优值。本实验只演示删除后的合并，不冒称完整原题交互。无需播放；按钮支持Tab/Enter，窄屏图可滚动，减少动画时停用过渡。
看完图，带走这些结论
欧几里得算法利用 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。因此每一步保留全部公因数。已切正方形与剩余矩形在原外框内无重叠、无遗漏。
逐步例子
- 48×18：48=2×18+12，横向切去两块18×18正方形，留下12×18矩形。
- 18=1×12+6，在余下区域切一块12×12，留下12×6矩形。原矩形没有旋转，数值运算始终先用长边除以短边。
- 12=2×6+0，切去两块6×6，余数为0。因此gcd(48,18)=6，不是0。
- 切分过程的大块尺寸不同；最终改用边长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没有前缀和相减的逆操作；数组改值后必须重建两侧表。
参考资料
教学结构参考 AetherViz Master（MIT）；原创原生 SVG 实现，无外部图形脚本。几何帮助观察，整除双向推导给出证明。