两把表，藏着同一道数学题 - 每日分享

把两把秒表同时按下去，一把表盘只有18个刻度，另一把有27个刻度。然后盯着它们转——你猜，当小表转完一圈时，两把表的指针有多少次指向同一个刻度？

答案是18次。但这不是巧合，而是模运算在背后敲钟。

钟表是理解模运算最好的启蒙老师。表盘只有12格，15点和3点在表盘上指向同一个位置，因为 15 % 12 == 3。在Python里，模运算用一个 % 符号搞定，它看起来简单，却是从判断奇偶到设计RSA加密都要用到的核心工具。

模运算，就是“分剩余数”

你有8块糖，分给3个小朋友，每人拿2块，剩2块。Python这样写：

candies = 8
kids = 3
remainder = candies % kids  # 2

就这么简单。但模运算真正的威力不在“简单求余”，而在于它能帮我们处理一切有周期规律的问题——星期几、报数、循环队列、密码学、校验码，全是它的主场。

比如今天是星期三，100天后是星期几？把星期一到星期天看成1到7，那么：

(3 + 100 - 1) % 7 + 1  # 结果是？

算出来是星期四。注意那个 -1 和 +1，是为了让结果落在1～7，而不是0～6。很多新手在这里栽跟头：余数为0时直接输出0，结果日历上根本没有星期0。

这是模运算最容易出错的点，也是题目最喜欢挖的坑。

同余：同一个世界，同一个余数

两个数除以同一个数，余数相同，就说它们同余。在Python里判断两个数是否同余，不是比大小，而是比余数：

print(25 % 12 == 13 % 12)  # True，都余1

23和11，模12也都余11，所以它们同余。这些数字在“模12的世界”里被当成同一个东西，就像钟表上3点、15点、27点，指向同一个位置。

同余的加减乘性质也很有用：如果a和b同余，c和d同余，那么它们的和、差、积仍然同余。编程中做大数乘法时，可以先把每个数取模，再相乘取模，结果不会变——这个技巧能防止溢出，在算法竞赛里几乎天天用。

直接给你一道题，看它考什么

考虑三个正整数a、b、c，找一个大于1的整数x，使得a、b、c除以x的余数相同，求x的最小值。

这道题考的就是同余的另一个等价转化：如果a、b、c除以x余数相同，那么a-b、a-c都能被x整除。换句话说，x是(a-b)和(a-c)的公因数。要求x的最小值（大于1），其实就是在求这两个差值的最大公约数——因为一组数的公因数中，最大的那个决定了所有公因数的集合，而最小的大于1的公因数正是最大公约数的某个因数？等等，这里要小心。

我们要求的是“满足条件的最小x”，而x可以是最大公约数的任意大于1的因数。如果最大公约数本身大于1，那它并不一定是最小解——比如a-b=6，a-c=10，gcd=2，那最小x就是2；但如果gcd=12，那x还可能取2、3、4、6，而其中2最小。所以不能直接输出gcd。你需要对gcd做质因数分解，找到它的最小质因子，那才是答案。

这里有个更直接的思路：x必须整除所有差值，因此x整除这些差值的gcd。而最小的x就是gcd的最小质因子（如果gcd>1）。题目保证有解，所以gcd一定大于1。

这道题让我想起一个经典问题：给定两个数，找最小的模数使它们同余——本质完全一样。

另一道题：两把表

回到开头的两把秒表。A表一圈18秒，B表一圈27秒，初始分别在18和27刻度。按下去之后，每秒走一格。问A转了n圈时，两表指针指向相同刻度的次数。

先想清楚：A表指针每秒到达的刻度是 t % 18（t从0开始，初始18在模18下是0），B表是 t % 27。指向相同，就是：

t ≡ 0 (mod 18) 且 t ≡ 0 (mod 27) ？

等等，这里两个表的“刻度”其实都是从0到17和0到26。初始A指向18，等同于刻度0；B指向27，等同于刻度0。所以两表指向相同刻度，等价于两个余数相等：

t % 18 == t % 27

这个等式什么时候成立？设 t = 18p + r1 = 27q + r2，且 r1 = r2 = r，那么 18p ≡ 27q (mod ... 不，直接看：如果余数相同，那么 t - r 同时被18和27整除，即 t - r 是 lcm(18,27) 的倍数。但 r 的范围是0到17（因为A表只有18个刻度），所以需要逐个验证。

更简单的解法是：直接枚举t从0到A转n圈的总秒数，每次判断 t%18 == t%27。但n可以到10^10，不能枚举。需要找规律。

观察：t%18 == t%27 意味着 t 除以18和27的余数相同。设 t = 18a + r = 27b + r，则 18a = 27b，即 2a = 3b，所以a是3的倍数，b是2的倍数。也就是说，t - r 是 lcm(18,27)=54 的倍数。那么对于固定的余数r，满足条件的t是 r + 54k。同时r必须小于18（因为要小于两个模数中较小的），并且 t 和 t%18 = r 确实成立？检查：如果 t = 54k + r，则 t%18 = (54k+r)%18 = r%18 = r（因为r<18），t%27 = (54k+r)%27 = r%27 = r（因为r<27）。所以任何r从0到17都可行。

所以条件就是 t ≡ r (mod 54)，其中r∈[0,17]。也就是说，每个长度为54的周期里，有18个时刻满足条件（r=0到17）。但注意r=0对应t为54的倍数，此时两表都指向0刻度，算一次。

那A表转n圈，总时间为 18n 秒（因为A表每18秒一圈，初始第0秒也在0刻度）。我们需要统计0到18n-1之间满足条件的t的个数？注意“当A秒表转了n圈时”指的是A表从0秒走到18n秒，总共走了18n秒，时刻t从0到18n（包含端点？），次数是指“指针同时指向相同刻度值的次数”，所以取t=0到18n（A表转了n圈就是刚好回到0刻度）。样例：n=1时，总时间18秒，t=0到18，满足条件的t为0,1,2,...,17,18？按规律每54周期有18个，但18<54，所以从0到18共有19个？但样例说是18次。看看：t=0时A指向0（初始18相当于0），B指向0，相同；t=1...17，相同；t=18时A指向0，B指向18？B刻度27一圈，18%27=18，不相同。所以t=18不算。所以应该是t从0到18n，但不包括t=18n吧？或者包括？n=1时18n=18，不包括18，只统计到17？那次数就是18。所以正确的统计是 t 从0到18n-1（或者等价的，[0, 18n)区间内），满足条件的个数。

好，那么问题转化为：在区间 [0, 18n) 内，有多少个整数t满足 t ≡ r (mod 54)，其中r=0,1,...,17。这就是模运算的周期计数问题。

每54个数中有18个，所以总次数大概是 18 * floor(18n/54) + 余数部分。但n是正整数，18n不一定是54的倍数。设总秒数T = 18n。周期长度L = 54。T/L = n/3。可以分情况：

如果n是3的倍数，T = 54k，那么[0, 54k)中每个周期18个，共18k = 6n 次。
如果n = 3k+1，T = 54k+18，完整周期有18k次，剩余[54k, 54k+18)区间，对应t=54k+r（r=0..17），全部满足，正好18次，所以总次数18k+18 = 18(k+1) = 6n+12？不对，6(3k+1)+12=18k+18，对。
如果n = 3k+2，T = 54k+36，完整周期18k，剩余[54k, 54k+36)区间，长为36，其中满足条件的是r=0..17，共18个（因为36<54，只有前18个r满足），所以总次数18k+18 = 18(k+1) = 6n？6(3k+2)=18k+12，不对。18k+18 = 6n+6。验证n=2时，T=36，满足t=0..17共18个？T=36，区间[0,36)，满足条件的t=0..17共18个。n=1时也是18。n=2应该也18？我们手动算一下：t=18时B是18，A是0，不同；t=19 A=1,B=19%27=19不同；... t=26 A=8,B=26不同；t=27 A=9,B=0不同；直到t=35 A=17,B=8不同。确实没有相同。所以n=2时次数=18。按上面结果6n=12不对。修正：n=3k+2时，总次数=18k+18=18(k+1)。而18(k+1) = 6(3k+3) = 6n？不对，6(3k+2)=18k+12。差了6。所以公式是18*ceil(n/3)? 因为每三分之一圈（18秒）有一组18次？n=1：18；n=2：18；n=3：36？验证n=3，T=54，[0,54)中满足t=0..17且t=54? 不，[0,54)正好一个周期，满足r=0..17共18个。那不对。等等，周期是54，一个完整周期内r从0到17，但是r=0时t=0,54,108... 在[0,54)内只有t=0一个。所以每个54周期18个。n=3时T=54，[0,54)长度54，完整周期，18个。所以n=1:18, n=2:18, n=3:18? 但直觉上A转3圈，B转2圈，应该更多次相同？我们重新想想。

问题在于：t=0时A和B都在0刻度，这是一次。t=18时A在0，B在18——不同。t=36时A在0，B在9？36%27=9，不同。那A每转一圈，只有初始时刻的t=0,18,36,54? A在0刻度的时刻是t=0,18,36,... 在这些时刻B的刻度是t%27：0,18,9,... 只有t=0和t=54（B%27=0）相同。所以A每圈都可能和其他时刻相同。

手动枚举n=1，t从0到17，两个表刻度相同：0: (0,0), 1:(1,1), ... 17:(17,17)，共18次。t=18: (0,18)不同。正确。

n=2，t从0到35：前18次相同，t=18-35没有相同，所以总次数18。对。

n=3，t从0到53：前18相同，t=18-35没有，t=36-53呢？t=36: A=0,B=9不同；t=37 A=1,B=10...; t=44 A=8,B=17; t=45 A=9,B=18? 45%27=18; ... t=53 A=17,B=26; 都没有相同。所以n=3还是18次。n=4呢？T=72，t=54: A=0,B=0相同一次！t=55 A=1,B=1? 55%27=1, 55%18=1，相同。所以从t=54到71又是18次。因此n=4总次数=36。规律：每3圈（54秒）出现一组18次。因为A转3圈是54秒，正好是lcm(18,27)=54，两表同时回到0刻度，然后重复。所以每3圈为一个大周期，其中前18秒有18次相同，后36秒没有相同。于是答案就是 18 * ceil(n/3)？n=1 -> 18, n=2 -> 18, n=3 -> 18, n=4 -> 36。或者更严谨：n圈中，完整的大周期（3圈）有floor(n/3)个，每个18次；剩余n%3圈：如果余1，包含第一圈的18次；如果余2，也还是那18次（因为第二圈没有额外相同）。所以总次数 = 18*(floor(n/3) + (1 if n%3>0 else 0))。也可以写成 18 * ((n + 2) // 3)（向上取整）。

这道题的精髓在于把“同时指向相同刻度”转化为模运算同余，然后发现周期是lcm(18,27)=54，而在每个54秒周期内只有前18秒满足。可见模运算的周期性质如何直接决定计数。

负数和余数：Python不同的地方

Python的 % 有个特性：结果的正负号和除数一致。-7 % 3 等于2，而不是-1。这与C/Java不同。数学上，同余关系允许余数取负数，但Python规定余数非负（除数正时），这反而带来方便：在计算循环下标时，永远不用担心负索引溢出。

print(-7 % 3)  # 2
print(7 % -3)  # -2

如果你希望“数学上标准”的余数，就用 (a % b + b) % b。

陷阱：同余不等于相等

25 % 12 == 13 % 12 为True，但25≠13。做同余判断时，比较的一定是 a % m == b % m。在编写星期推算、循环队列时，还要留意余数为0的情况：通常用 (index - 1) % n + 1 把结果映射到1到n区间，避免出现第0个。

看一眼真正的应用

除了算法题，模运算在现实中无处不在：

判断闰年：(year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)
身份证校验码：用模11计算最后一位
RSA加密：大模幂运算
伪随机数生成器：递推式里全是模运算

如果你已经会了模运算的基础，可以进一步研究同余方程和欧几里得算法。最大公约数的辗转相除法就是反复用 % 直到余数为0。学会了它，上面的“余数相同问题”就能一眼看穿：a、b、c除以x余数相同，等价于x整除(a-b)和(a-c)，所以x是所有公因数的因子，最小解就是这些差值的最大公约数的最小质因子。把问题转化成gcd，思路瞬间清晰。

模运算就像一把钥匙，打开了一扇叫做“周期”的门。门后是数论的世界，而Python的 % 就是你手上最趁手的工具。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）