利用同余定理,在循环乘法过程中步步对 100 取模,防止溢出。
OJ: roj
题目 ID: 5026
难度:入门
标签:循环结构同余定理取模
创建: 2026-10-08 22:34
更新: 2026-10-08 22:34
形式化题目
输入一个整数
正解
思路
根据题意,我们需要计算
如果直接计算 long long 的存储范围,发生溢出。为了避免溢出,可以运用同余定理:两个整数乘积的末两位数,只与这两个整数各自的末两位数有关。用数学语言表述就是:
因此,我们在用循环求乘积的过程中,不需要保存真实的积,只需在每次乘完
因为本题的数据范围上界
代码
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 22:24
# update_at: 2026-10-08 22:24
import sys
def last_two_digits(n: int) -> int:
"""同余定理步步取模:与 C++ 主解同算法、同为 O(n)(不用 pow 的三分幂,见题解说明)。"""
res = 1 # 乘法单位元;n = 0 时输出 1,但该边界题面未定义、数据未覆盖
for _ in range(n):
res = res * 1992 % 100 # 中间结果恒小于 100 * 1992
return res
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
print(last_two_digits(n)) # 按整数输出,不补前导零(n = 111 的答案文件是 "8" 而非 "08")
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 22:24
* update_at: 2026-10-08 22:26
*/
#include <cstdio>
typedef long long ll;
// 求 n 个 1992 的乘积的末两位:同余定理 (a*b) mod 100 = ((a mod 100)*(b mod 100)) mod 100
ll last_two_digits(ll n) {
ll res = 1; // 乘法单位元(n = 0 时输出 1,该边界题面未定义、数据未覆盖)
for (ll i = 1; i <= n; ++i) {
res = res * 1992 % 100; // 步步取模,中间结果恒小于 100 * 1992,不会溢出
}
return res;
}
int main() {
ll n;
if (scanf("%lld", &n) != 1) {
return 0;
}
// 真实数据按整数输出,不补前导零(n = 111 的答案文件是 "8" 而非 "08")
printf("%lld\n", last_two_digits(n));
return 0;
}复杂度
- 时间复杂度:
,循环执行 次,每次做常数时间的乘法和取模运算。Python 版本为对齐 C++ 且贯彻本题的教学目的,也使用了 的循环,而不是内部实现为 的 pow(1992, n, 100)函数(在时耗时依然微乎其微)。 - 空间复杂度:
,只需要保存当前的乘积和循环变量,不依赖输入规模。
总结
本题看似非常简单,但却有两个极其隐蔽的坑(题意与测试数据不符的暗礁):
- 输出格式的大坑(是否补零)
- 题面要求输出「末两位数」,但 测试数据对个位结果没有补零。
,其幂次 从 起是一个纯周期为 20 的循环。在 的范围内,有整整 200 个 的结果 (例如 )。 - 反事实测试(V1 验证):如果按字面意思把输出改成
%02lld或f'{ans:02d}',一字不改重新评测,会获得 8 PASS / 2 FAIL 的结果(命中判别点 6、判别点 10 报错)。因此本题绝对不能进行前导零格式化,必须使用 %lld/ 裸print输出。
- 隐藏的
边界问题 - 题面只给出了
这个上界,只字未提下界,也没有说它是正整数。 - 数据中
,并未覆盖 。所以 属于「题意未定 + 数据未覆盖」的地带。代码中初始 res=1即是约定输出 1。 - 旁证:
,这意味着只要 ,真实答案一定恒为 4 的倍数( )。而 时答案是 1(非 4 的倍数),这是唯一破坏倍数结构的特例,反过来说明出题人潜意识里的数据必然不包含 0。
- 题面只给出了
最后,本题的测试严密性已经过极高强度验证:利用 Python 原生大整数 $1992**n \bmod 100$ 对 {0, 1, 100, 1992})与最终跑出的答案值交集为空,杜绝了硬编码猜测的可能。