GCD、LCM 与欧几里得算法

① 第二问那个 -1： 一道纯粹的「求 lcm」在 n = 10⁵ 时答案会大到没法写。 加了上限之后，「什么时候该判溢出、判在哪一句」就成了题目的一部分 —— 而这正是数学这一块最容易翻车的地方。 ⚠ 第 10 步会看到：三个和溢出有关的错误版本，要求的数据规模一个比一个高。

② 第三问那个前缀 gcd： 它是「题面多问一句」的第六次（第 35~39 章连着五次）。 这一次多问的东西很朴素 —— 它逼你把中间过程也算对，而不是只交一个最终答案。 第 11 步会看到，它正好卡住一个只错在中间过程上的 bug。

⚠ 而它还有一个副作用，是写完之后才发现的：这一行让「随机数据把题目做没了」这件事变得看得见 —— 随机数据上这一行几乎恒等于 a₁ 1 1 1 …。

8
12 18 30 5 60 7 1000000007 907696939

第一行 gcd = 1        （12,18 → 6；6,30 → 6；6,5 → 1，之后就一直是 1）
第二行 lcm = -1       （lcm 到 1260 × 1000000007 = 1.26×10¹², 再乘 9 亿 → 超 10¹⁸）
第三行 前缀 gcd = 12 6 6 1 1 1 1 1

三处特意安排：

• 前三个数带公因子（12、18、30 → 6），第四个数 5 一来 gcd 就掉到 1 —— ★ 这样第三行才有内容可看，而不是从第二项开始就一路 1；
• gcd(30,5) = 5 而 gcd(12,18,30,5) = 1 ——「前缀 gcd」和「相邻两个的 gcd」在这里分道扬镳；
• 最后两个是九位数，而且和前面互质 —— lcm 一步跨过 10¹⁸。

⚠ 前六个数完全可以手算；后两个是给溢出准备的，得靠代码。这一点得说明白， 别假装那两个数也是手算出来的。

每个质因子的 min + max = 两个指数之和，于是

gcd(a,b) × lcm(a,b) = a × b

—— 这就是代码里那句 lcm = a / gcd(a,b) * b 的来历。 ⚠ 而为什么要先除后乘，第 7 步再说，那是这一章一半的坑。

秒表失灵就数次数（第 21 章以来的老规矩）。可这一章有个新麻烦： 相减法在 gcd(10⁹, 1) 上要减十亿次，真跑一次要按秒算，三百轮就按分钟算。

好在这两个数都有闭式，一行就能算出来：

★ 这是这本书第一次用「算」的方式给出计数器，理由很实在：跑不动。 而它和「跑出来」是同一个数 —— 前两行是定义，后两行是循环边界。

点「运行 ▶」看结果

实测（./genBig 2 档位，全部写进了 check:viz）：

★★ 这张表里藏着这一章最漂亮的一句话，在斐波那契那一行：

取模 43 步，相减 44 步 —— 几乎一样。 因为斐波那契那一档每一步的商都是 1，而「取模」本来就是「一口气减 q 次」的缩写。 ⇒ 斐波那契之所以是取模法的最坏情况，恰恰因为那时候取模退化成了相减。

⚠ 最后一行也值得单看：brute（分解质因数）只看这个数本身有多大，不看两个数的关系 —— 所以别人都一步到头的时候，它还得老老实实试 63 242 次。

设 a = k·b + r（r = a mod b）。

• 若 d | b 且 d | r，那么 d | (k·b + r) = a ⇒ d 是 (a,b) 的公约数；
• 若 d | a 且 d | b，那么 d | (a − k·b) = r ⇒ d 是 (b,r) 的公约数。

⇒ 两对数的公约数集合完全相同，那么其中最大的那个当然也相同。∎

★ 这一步值钱的地方在于它换了个对象去证： 直接去比「两个最大值谁大谁小」是证不动的， 把问题换成集合相等，一行就完事了。

第 19 章的交换论证（别盯着最优解，去看「把它变成我的解」的过程）、 第 34 章的切割性质（别盯着最小生成树，去看一条切割边）—— 都是同一种手法：证不动的时候，换一个更大的对象去证。

设 a ≥ b，看 a mod b：

• 若 b ≤ a/2，那么 a mod b < b ≤ a/2；
• 若 b > a/2，那么 a mod b = a − b < a/2。

两种情况都得到 a mod b < a/2 ⇒ 两步之内第一个数至少减半 ⇒ O(log a)。

⚠ 但这只是个上界。真正的最坏情况长什么样、随机数据能不能碰到它，第 9 步专门量。

★ 「值域拧满」在这一章不是开关，是一把有三个刻度的旋钮。 ⚠ 而甲组要「gcd 会变成 1」、乙组要「有公因子」—— 这两组是打架的，第 11 步会看到代价。

★ 后三个一模一样 —— 光看这一组数据，你分不清是哪一个 bug。

⚠ 这件事本身要写进正文：「对拍抓到了」和「我知道错在哪」是两回事。 三个 bug 都会让那一乘绕回去，绕回去之后的那个数当然一样。

★ 而 wrongBreak 的那个 180 是最好玩的：if (g == 1) break; 这句话对第一问完全正确 （gcd 一旦是 1 就再也变不回去），它只是顺手把后面那些数也跳过了 —— 于是 lcm 只算了前四个数。

★ 一个只对「其中一问」成立的剪枝，被顺手用在了整个循环上。

① ⚠ 档位 1 是这一章的反面教材。 我按上面那条「随机数据把题目做没了」去补公因子，一口气全加上 —— 结果 wrongOne 从 263 掉到 12、wrongBreak 从 147 掉到 4。 道理很直白：甲组那两个 bug 要的正是「gcd 会变成 1」，我把这条路堵死了。

★ 第 31 章那条「某一支永远走不到是坑，某一支占得太多也是坑」的又一次现场 —— 而这次是我照着上一条教训做，做过了头。 ⇒ 改成「只给一半的数乘公因子」（档位 2），Prefix 涨到 195，甲组也活了下来。

② ⚠⚠ 而全场最大的功臣，是一个和直觉相反的旋钮：把 n 压短。 最弱支 56 → 116，翻了一倍还多，而且 wrongNoLim 直接满分。 为什么？wrongLate 只在溢出那一步的乘积撞破 long long、而且绕回去之后落在 10¹⁸ 以内时才现形； n 一大，它绕回去之后后面还有好几次乘法，迟早会有一次让 l > 10¹⁸ 成立 —— 于是它蒙对了 -1。

★★ 数据越多越容易抓 bug，这句话在这里是反的。

③ ⚠ 对照着看档位 4（n 拉长）就更清楚了：它把 wrongOne 顶到 300、wrongPrefix 顶到 297， 看着是全表最漂亮的一档 —— 可它同时把两个溢出 bug 打成 0 和 5。

★★ 同一个旋钮的两头，正好是两组 bug 的天堂和坟墓。 （第 38 章「n 是不是 2 的幂」那次的第二次现场，这次的旋钮是 n 本身。）

① 「混入 1」是负分，撤回（117 → 89）。第 32、34、35、37、39 章那条调优不可加的又一次。

② ⚠ 而档位 10 那笔账要老实写：它是有用的，可我没留。 加上「一半的数乘公因子」之后：wrongPrefix 131 → 162， 而且 300 轮里 gcd ≠ 1 的从 32 轮涨到 94 轮（边界覆盖实打实变好了）。 代价是最弱支从 117 掉到 95。

★★ 这和第 38 章那次判据相同、结论相反，值得并排记一次： · 第 38 章为了边界覆盖留下了一个抓获率略差的旋钮（最弱支 222 → 207，掉 7%）； · 这一章同样是为了边界覆盖，可代价是 117 → 95（掉 19%）—— 太贵，不留。 ⇒ 判据从来只有一条（让最弱的那一支尽量强），变的是代价有多大。 ⚠ 但那一支不能没有，所以它作为可重跑的档位 10 留在生成器里 —— 读者随时能跑到「数据带公因子」的那一支。

递归回来时已经有 b·x' + (a mod b)·y' = g，而 a mod b = a − ⌊a/b⌋·b，代进去：

b·x' + (a − ⌊a/b⌋·b)·y' = a·y' + b·(x' − ⌊a/b⌋·y') = g

⇒ x = y’，y = x’ − ⌊a/b⌋ · y’。边界：b = 0 时 (x, y) = (1, 0)。∎

★ 它顺带证明了裴蜀定理：a·x + b·y 能取到的最小正整数正好是 gcd(a,b) —— 于是「a·x + b·y = c 有整数解 ⟺ gcd(a,b) | c」。第 42 章求逆元时会直接用它。

点「运行 ▶」看结果

⚠ 两个细节：

• 验算必须用 __int128：a、b 到 10⁹ 时 a·x 会超 long long（x 本身能到 10⁹ 量级）。
• 看那一行 gcd(121393, 75025) = 1，x = 28657，y = −46368 —— ★ 全是斐波那契数。 最坏输入的系数也长在同一个数列上，不是巧合。