【例4.11】体操队

GitHub跳转原题关系图返回列表

求解满足一系列同余条件的最小正整数(中国剩余定理的特例),可以通过直接从小到大枚举来解决。

OJ: roj

题目 ID: 5027

难度:入门

标签:循环枚举同余

创建: 2026-10-08 16:17

更新: 2026-10-08 16:17

形式化题目

已知一个正整数 nn,满足以下条件:

  1. n mod 2=1n \bmod 2 = 1
  2. n mod 3=1n \bmod 3 = 1
  3. n mod 4=1n \bmod 4 = 1
  4. n mod 5=1n \bmod 5 = 1
  5. n mod 6=1n \bmod 6 = 1
  6. n mod 7=0n \bmod 7 = 0

求满足上述条件的最小的 nn。 注意:本题无输入。

正解

思路

题目要求一个数 nn,使得它除以 2,3,4,5,62, 3, 4, 5, 6 都余 11,并且是 77 的倍数。 即求满足以下同余方程组的最小正整数解:

{x≡1(mod2)x≡1(mod3)x≡1(mod4)x≡1(mod5)x≡1(mod6)x≡0(mod7) \begin{cases} x \equiv 1 \pmod 2 \\ x \equiv 1 \pmod 3 \\ x \equiv 1 \pmod 4 \\ x \equiv 1 \pmod 5 \\ x \equiv 1 \pmod 6 \\ x \equiv 0 \pmod 7 \end{cases}

这其实是「中国剩余定理」的一个简单版本。因为这道题对 nn 的要求很简单,且答案很小,我们可以直接用计算机程序从小到大暴力枚举 nn: 从 n=1n = 1 开始,依次检查是否同时满足这 66 个条件。遇到第一个满足所有条件的数就是所求的最少人数。 甚至我们可以做一些剪枝,只枚举 77 的倍数,即 n=7,14,21⋯n = 7, 14, 21 \cdots,再检查前面几个条件,这样能让循环次数更少。 不过由于答案 301301 非常小,直接从小到大挨个枚举也只需要不到 400400 次循环,瞬间就能完成。

从数学上来说: 前五个条件可以合并为 n≡1(modlcm⁡(2,3,4,5,6))n \equiv 1 \pmod{\operatorname{lcm}(2,3,4,5,6)}。 因为 lcm⁡(2,3,4,5,6)=60\operatorname{lcm}(2,3,4,5,6) = 60,也就是 n=60k+1n = 60k + 1。 把 k=1,2,3,4,5⋯k=1,2,3,4,5\cdots 试进去,发现 k=5k=5 时 n=301n=301 是 77 的倍数,这就是最小正整数解。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 16:12
# update_at: 2026-10-08 16:12

from itertools import count


def solve() -> None:
    """本题无输入:从 7 的倍数起枚举,首个满足「每行 2..6 人都多出 1 人」的人数即最少人数。"""
    answer = next(n for n in count(7, 7) if all(n % k == 1 for k in range(2, 7)))
    print(answer)


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 16:12
 * update_at: 2026-10-08 16:13
 */
// main.cpp:本题无输入,直接从小到大枚举满足全部同余条件的最少人数。
#include <iostream>

typedef long long ll;

int main() {
    // 人数必须是 7 的倍数,所以从 7 开始每次加 7 枚举;
    // 首个同时满足「每行 2..6 人都恰好多出 1 人」的 n 就是最少人数。
    for (ll n = 7; ; n += 7) {
        if (n % 2 == 1 && n % 3 == 1 && n % 4 == 1 && n % 5 == 1 && n % 6 == 1) {
            std::cout << n << "\n";
            return 0;
        }
    }
    return 0; // 不会到达
}

复杂度

  • 时间复杂度:O(ans)O(ans),其中 ans=301ans = 301,程序运行步数与答案大小成正比。常数极小,时间复杂度可以认为是 O(1)O(1)。
  • 空间复杂度:O(1)O(1),只需要常数级别的变量存放数值。

总结

  • 经典的小学奥数/数论入门题,熟悉同余、整除的概念与 % 运算符的使用。
  • 题目要求无输入直接给出答案。有些情况下也可以自己手算得出结果后直接打印,但写一个简单的枚举程序更容易验证结果的正确性。
  • 代码实现时要注意从 11(或者 77)开始循环,而且退出条件是所有条件同时满足,可以使用 && 操作符连结各个判断。