#8879. 爱因斯坦的数学题(简单循环)
爱因斯坦的数学题(简单循环)
最少阶梯数问题
版权信息:
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
最少阶梯数计算 | 1 sec | 512 MB | 100 points |
题目描述
爱因斯坦曾提出一道数学题:
有一条长阶梯,满足以下条件:
- 每步跨 2 阶,最后剩 1 阶。
- 每步跨 3 阶,最后剩 2 阶。
- 每步跨 5 阶,最后剩 4 阶。
- 每步跨 6 阶,最后剩 5 阶。
- 只有每步跨 7 阶,最后才刚好不剩阶梯。
请你计算 这条阶梯最少的阶数。
输入格式
无输入。
输出格式
输出 阶梯的最小阶数。
样例
输入
(无输入)
输出
119
题目分析
题目要求 **最小的正整数 n
**,满足:
n % 2 == 1
n % 3 == 2
n % 5 == 4
n % 6 == 5
n % 7 == 0
可以转化为 同余方程组:
解法
我们可以从 n = 7
开始 逐步寻找满足条件的最小值:
n
必须是7
的倍数 (n = 7k
)。- 依次验证是否满足
mod 2, 3, 5, 6
的约束。
时间复杂度分析
n
以7
的倍数递增,最坏情况O(7k) ≈ O(k)
。k
远小于n
,因此 **复杂度可视为 O(1)**。
总结
- 采用 逐步枚举(
n += 7
)。 - 找到 最小的 n 满足
mod 2, 3, 5, 6, 7
约束。 - 复杂度 **O(1)**,适用于小范围整数计算。
统计
相关
在以下作业中: