求解满足一系列同余条件的最小正整数(中国剩余定理的特例),可以通过直接从小到大枚举来解决。
OJ: roj
题目 ID: 5027
难度:入门
标签:循环枚举同余
创建: 2026-10-08 16:17
更新: 2026-10-08 16:17
形式化题目
已知一个正整数
求满足上述条件的最小的
正解
思路
题目要求一个数
这其实是「中国剩余定理」的一个简单版本。因为这道题对
从数学上来说:
前五个条件可以合并为
代码
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; // 不会到达
}复杂度
- 时间复杂度:
,其中 ,程序运行步数与答案大小成正比。常数极小,时间复杂度可以认为是 。 - 空间复杂度:
,只需要常数级别的变量存放数值。
总结
- 经典的小学奥数/数论入门题,熟悉同余、整除的概念与
%运算符的使用。 - 题目要求无输入直接给出答案。有些情况下也可以自己手算得出结果后直接打印,但写一个简单的枚举程序更容易验证结果的正确性。
- 代码实现时要注意从
(或者 )开始循环,而且退出条件是所有条件同时满足,可以使用 &&操作符连结各个判断。