余数就是分组 — 10 的 100 次方天以后是星期几
这一章讲三件事: 余数为什么能把一个大到算不动的数一次降成小数; 「余数就是分组」这句话具体指什么; 以及碰上连除法都做不了的数时,那条固定的破解套路。
它在全书链条里的位置: 前五章讲的是「怎么把条件切干净」。 从这一章开始换工具:不切了,改成换个角度看。 这一章看的是「除以几余几」,第 07 章会把它压到极致——只看单双。 不需要前面几章的基础,会做除法就行。
1. 先看现象:今天星期日,100 天以后是星期几
你可以一天 天数。 明天星期一、后天星期二……数到第 100 天。 这确实能数出来,因为 100 不算大1。
也可以这么想: 一周七天,每过 7 天就转回同一个星期数。 98 是 7 的倍数,所以第 98 天还是星期日;那么 99 天后是星期一,100 天后是星期二2。
再换一种,一步到位:
把星期数当成 0 到 6 的编号
────────────────────────────────────────
0 1 2 3 4 5 6
日 一 二 三 四 五 六
────────────────────────────────────────
100 ÷ 7 = 14 …… 余 2 → 星期二
图说:今天是星期日(编号 0),n 天后的星期数就是 n 除以 7 的余数。
全章的主走查从这一步开始,最后要走到 10 的 100 次方天。
一次除法,答案就出来了3。这是主走查的第一步。
2. 换成一亿天:数不动,可除法还是一秒的事
这一节回答:上一节那三种办法看着差不多,差别在哪。
把 100 换成 1 亿。
数数这条路当场断掉: 就算一秒数一下,数到一亿也要三年以上4。
除法这条路一点没变:
100 000 000 ÷ 7 = 14 285 714 …… 余 2 → 还是星期二
这是主走查的第二步5。同样一秒钟,同样一次除法。
这就是余数的本事:它不是省一点力气,是把力气从「跟着数变大」变成「不跟着数变大」。 一亿天和一百天,除法的工夫是一样的;而数数的工夫差了一百万倍。
为什么能这样?因为星期数是以 7 为周期循环的6。 只要一件事在转圈,你就不必跟着它走完全程,只要知道它停在哪一格。
3. 「余数就是分组」是什么意思
这一节回答:上面那句「停在哪一格」怎么理解得更牢。
原书给了一个特别好用的画面:把周期为 7 想象成一个七角形的时钟7。
日(0)
六(6) 一(1)
● ← 指针
五(5) 二(2)
四(4) 三(3)
图说:七个顶点写上 0 到 6。指针一天走一格,七天走一圈。
「100 除以 7 商 14 余 2」的意思是:指针转了 14 圈,又多走了 2 格。
商是圈数,余数是最后停在哪一格 —— 只有余数决定答案。
于是「余数」这个词有了第二层意思:它是一张分组的标签。 所有天数被分成 7 组:除以 7 余 0 的一组、余 1 的一组……余 6 的一组。 同一组里的天数,星期数完全相同——第 1 天、第 8 天、第 15 天都是星期一。
这就是这一章的标题:余数就是分组8。 你不需要知道一个数具体是多少,只需要知道它属于哪一组。 (第 07 章会把组数压到最少的 2 组,那时这一招会显出更狠的一面。)
4. 真正的考验:10 的 100 次方天以后是星期几
这一节是主走查的重头戏。
10 的 100 次方是 1 后面跟 100 个 09。 按上一节的办法,应该拿它除以 7——但这个数太大,连计算器都算不动10。
原书的办法是:既然除不动,就先拿小的试,看有没有规律。 把 0 的个数从 0 开始一个个加上去11:
| 0 的个数 | 那一天是第几天 | 除以 7 的余数 | 星期几 |
|---|---|---|---|
| 0 | 1 天后 | 1 | 星期一 |
| 1 | 10 天后 | 3 | 星期三 |
| 2 | 100 天后 | 2 | 星期二 |
| 3 | 1000 天后 | 6 | 星期六 |
| 4 | 1 万天后 | 4 | 星期四 |
| 5 | 10 万天后 | 5 | 星期五 |
| 6 | 100 万天后 | 1 | 星期一 ← 和第一行一样了 |
| 7 | 1000 万天后 | 3 | 星期三 ← 和第二行一样了 |
余数按 1、3、2、6、4、5 循环,每 6 个一转12。这是主走查的第三步。
注意这里发生了什么:第一次除法要除的数是天数,除数是 7; 现在要除的数变成了「0 的个数」,除数变成了 6。 换了一层楼。
10 的 100 次方有 100 个 0,所以:
100 ÷ 6 = 16 …… 余 4 → 查上面那张表,余 4 对应星期四
答案:星期四13。这是主走查的第四步,也是终点。
再往上走也不怕。 原书顺手算了「10 的一亿次方天以后」: 一亿除以 6 余 4,还是星期四14。 (作者在这里补了一句:当然,恐怕到那时宇宙都已经消失了。)
5. 同一套动作,换一道题再走一遍
这一节另起一处走查,用来验证上面那套动作不是这道题专用的。
题目:1 234 567 的 987 654 321 次方,个位数是几?15
这个数根本写不出来——用计算器算不出,写程序算也因为位数太多而不简单16。
但题目只问个位。 而影响乘方结果个位的,只有原数的个位17—— 1 234 567 的十位以上根本不参与个位的计算。所以只要看 7 的乘方18:
| 7 的几次方 | 个位 |
|---|---|
| 1 次方 | 7 |
| 2 次方 | 9 |
| 3 次方 | 3 |
| 4 次方 | 1 |
| 5 次方 | 7 ← 转回来了 |
个位按 7、9、3、1 循环,周期是 4。 于是拿指数除以 4: 987 654 321 ÷ 4 余 1,对应第一格,答案是 719。
和上一节比一比,动作完全一样: 先拿小的试算 → 找出循环 → 用余数落到某一格。换的只是「几个一循环」。
6. 把套路写下来,以及一个要留到第 14 章的伏笔
这一节把前面五节收成一条能带走的流程。
碰上「大到算不动」的数,四步:
────────────────────────────────────────────
① 先别算,拿小的数试:1、10、100、1000…
② 把结果排成一列,盯着看有没有转回来
③ 数出「几个一循环」——这就是周期
④ 拿要求的那个数除以周期,余数落在哪一格,答案就是哪一格
────────────────────────────────────────────
图说:两道题都是这四步。第一道题的周期是 6,第二道题的周期是 4。
难的不是除法,是第 ② 步 —— 你得先相信「它可能在转圈」。
原书对这套动作的总结是:在处理难以计算的超大数字时,发现与之相关的规律相当重要, 而余数正是有效利用规律的工具20。
最后留一个伏笔。 这一章第 4 节做了一件很特别的事: 它不再看那个数本身,改看「0 的个数」。 原书在这里点了一句:这和「对数」的概念有着密切的关系21。 「只数 0 的个数」这件事,到第 14 章会正式成为一件工具。
7. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| n 天后的星期数 = n 除以 7 的余数 | 给了理由:星期数以 7 为周期循环 |
| 10 的 100 次方那道题 | 给了完整走查:12 行试算表 + 两次除法 |
| 余数就是分组 | 给了画面(七角形时钟),没有给严格定义 |
| 「找规律」这件事 | 给了两道题的示范,但没有给「怎么保证真的有规律」的判据 |
判断(我们的,不是书里的):这一章教的其实是一种「先侦查再动手」的习惯。 两道题的共同点是:正面硬算都不可行,而试算三五个小数就能看出出路。 程序员对这件事往往有抵触——「先试几个小的」看起来像笨办法, 但它恰恰是唯一能在动手前发现「这题有捷径」的办法。 如果错,会错在: 试算看到的「规律」可能是巧合,前几项对上了后面就散了。 这一章的两道题都没有证明周期一定成立(证明要等第 08 章的数学归纳法)。 判据是:你能不能说出这个循环为什么必须一直转下去。
这一章的边界:
- 两个周期(6 和 4)都是试算试出来的,书里没有证明它们一定成立—— 严格来说这需要数论里的定理,原书刻意没碰;
- 没有讲负数的余数(不同语言里
-7 % 3的结果并不一致); - 没有讲余数在校验、散列、循环队列这些工程场合的用法,只有星期数与个位数两道题;
- 「余数就是分组」只给了画面,那套分组在数学上的正式名字(同余类)书里没提。
8. 可带走的
- 一件事在转圈,你就不必跟着走完全程,只要知道它停在哪一格;
- n 天后的星期数 = n 除以 7 的余数——因为星期是 7 天一转;
- 余数的收益不是省力气,是让力气不再跟着数变大:一亿天和一百天,除法工夫一样;
- 余数是一张分组标签:除以 7 余 1 的所有天数,星期数完全相同;
- 数大到除不动时,换一层看:10 的 100 次方看不了,就看它有几个 0;
- 破解套路四步:拿小的试算 → 排成一列 → 数出周期 → 用余数落格;
- 乘方的个位只由底数的个位决定;7 的乘方个位按 7、9、3、1 循环,周期 4;
- 试算出的「规律」还不是证明——它只是让你敢往下走,证明是第 08 章的事。
9. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 100 天后是星期几 | 第3章 余数 | text/08-ch03.txt:41(搜「98 是 7 的倍数」) · :60(搜「100 天后的星期数就是」) |
| 一亿天与数数的代价 | 第3章 余数 | text/08-ch03.txt:72(搜「数到 1 亿至少也要花费 3 年以上」) · :75(搜「100 000 000 ÷ 7 = 14 285 714 余 2」) · :78(搜「因为星期数是以 7 为周期循环的」) |
| 七角形时钟 | 第3章 余数 | text/08-ch03.txt:168(搜「七角形时钟」) · :171(搜「表示这个时钟前进 100 个刻度后指针指向」) |
| 10 的 100 次方那道题 | 第3章 余数 | text/08-ch03.txt:107(搜「由于数字太大了，计算起来相当费力」) · :131(搜「余数以 1, 3, 2, 6, 4, 5」) · :147(搜「100 ÷ 6 = 16 余 4」) · :149(搜「天以后是星期四」) |
| 乘方的个位数 | 第3章 余数 | text/08-ch03.txt:214(搜「无法用计算器算出来」) · :226(搜「能影响一个数乘方结果的个位数的」) · :243(搜「个位是 1, 7, 9, 3 这 4 个数字的循环」) · :250(搜「所以答案为 7」) |
| 找规律与余数的关系 | 第3章 余数 | text/08-ch03.txt:162(搜「发现与之相关的规律是相当重要的」) · :202(搜「这和「对数」的概念有着密切的关系」) |