#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

可以转化为 ​同余方程组​: image


解法

我们可以从 n = 7 开始 ​逐步寻找满足条件的最小值​:

  • n 必须是 7 的倍数 (n = 7k)。
  • 依次验证是否满足 mod 2, 3, 5, 6 的约束。

时间复杂度分析

  • n7 的倍数递增,最坏情况 O(7k) ≈ O(k)
  • k 远小于 n,因此 ​**复杂度可视为 O(1)**​。

总结

  • 采用 ​逐步枚举​(n += 7)。
  • 找到 最小的 n 满足 mod 2, 3, 5, 6, 7 约束。
  • 复杂度 ​**O(1)**​,适用于小范围整数计算。