那些让你崩溃的编程题-阶乘之比
点击我返回帖子索引
欢迎来到《那些让你崩溃的编程题》系列的第三期帖子~~~
首先，先来统一回复一下大家的疑问：TouchFish到底是什么网站呢？
其实，这个 OJ 测评网站是哎呦的同学pztsdy创建的，而这道题就是哎呦曾经遇到过，但是找不到原题的，所以以后但凡看到放在 TouchFish OJ 里的题目，都是哎呦的亲身经历，大家不要怀疑啦……
好了，依旧闲话不多说，以下是该题的具体内容（经过了哎呦的精心改动）：
E1006 阶乘之比
题目描述
有两个整数 n 和 m，现在要求出他们的阶乘之比比值的个位数。请你帮帮杨梅解出这道题吧。
输入格式
输入一行两个整数 n，m。
输出格式
输出一个一位整数，表示两个数阶乘之比比值的个位数。
输入输出样例
输入数据 #1
4 6
输出数据 #1
0
输入数据 #2
107 109
输出数据 #2
2
说明/提示
样例解释
样例 1 中，4 的阶乘计算为 1×2×3×4=24；6 的阶乘计算为 1×2×3×4×5×6=720。用 6 的阶乘除以 4 的阶乘，即 720÷24=30，结果的个位数字是 0。
样例 2 中，109 的阶乘除以 107 的阶乘，计算结果为 11772，这个结果的个位数字是 2。
数据范围
- 对于 20% 的测试数据，满足 2 ≤ n ＜ m ≤ 10²；
- 对于 60% 的测试数据，满足 2 ≤ n ＜ m ≤ 10⁹；
- 对于 100% 的测试数据，满足 2 ≤ n ＜ m ≤ 10¹²。
ps:原题的数据范围是 10 的 18次方，这里稍有改动，但还是足以让人崩溃了
题目解析+做题过程
一看到这个题的数据范围，哎呦的脑海里就不禁浮现出这样的画面：
（好吧，感觉比这个还要夸张）
可是，想归想，题目还是要做的。这题要求两个数的比值，其实就是求 m! 除以 n! 的个位数是多少。
由此，我们就能得到此题最——简单粗暴的方法：先算出两个数的阶乘分别是多少，并相减，最终的结果就是答案。
什么？你说会超时？管他呢！哎呦三下五除二，写出了一份这样的代码（其实是因为当时没注意看数据范围）：
int cnt1 = 1;
for(int i = 1;i <= n;i++){
cnt1 *= i;
}
int cnt2 = 1;
for(int i = 1;i <= m;i++){
cnt2 *= i;
}
printf("%d\n",(cnt2 - cnt1) % 10);
然后，这段代码成功的……超时了。
那么，我们来简单分析一下：
如图，假设 n 和 m 两个数分别为 4 和 6，那么它们的阶乘相除得到的数进行抵消，
题目就转换成了求 m-(n+1) 的阶乘是多少了。
这不就简单了吗？肯定可以通过！哎呦直接“噼里啪啦”一阵乱按，打出了一段这样的代码：
//ps：代码中的a和b分别对应题目中的n和m
int a,b;
scanf("%d%d",&a,&b);
int ret = 1;
for(int i = a + 1;i <= b;i++){
ret *= i;
ret %= 10;
}
然后，果然如此：
到底是哪里出了问题呢？哎呦把代码翻来覆去地看了半小时，最终发现……
int的范围：2³¹-1 = 2147483647
题目的数据范围：10¹⁸ = 1000000000000000000
long long的范围：9223372036854775807
十年 OI 一场空，不开 long long 见祖宗。 ——CCF
好吧，long long大神我错了……
那么，真的就是改个 long long 这么简单吗？
哎呦把代码所有的地方全改成了 long long 的升级版——unsigned long long，再次运行，结果……
再次时间超限……………………………………
这个题到底想干什么啊！！！！！
接着，哎呦再次尝试了多种办法。
- 直接推倒重建，写一份新代码？
- 在现有代码的基础上想破脑袋修改？？
- 直接打表通过所有样例？？？（这个是最阴的）
- ……
就在哎呦走投无路之际，一个善良的小盆友给了哎呦建议：
对啊！既然瞪眼看不出问题，干脆直接上邪修——哪里能优化我在哪里补特判，啥也优化不了我就硬加！
我们来想想：
如果在循环过程中，发现这个 ret 已经是 10 的倍数，是不是可以说明，最终的结果也一定是 10 的倍数?
而 10 的倍数的末尾也总是 0，这代表，我们可以在循环中途加上这样一个特判来解决问题：
if(ret % 10 == 0){
printf("%d\n",0);
return 0;
}
验证一下：
假设 n=3，m=6：
n! =1×2×3
m! =1×2×3×4×5×6
当循环执行到 i=5 时，ret的值为 20，如果按照一开始的思路算下去，20*6=120，个位数为 0；
如果按照新的优化思路执行，当识别到ret为 20，个位数为 0 后，程序自动输出 0 并结束，正好可以正确！
这还说什么啊？哎呦立刻迫不及待地吧这份代码提交了上去。果然……通过啦！
这个故事告诉我们：有时候瞪眼法和邪修才是题目的正解，不要老想着去推倒重建……
其实这个题本身并不是很难，只不过有一些很恶心的数据点……
好了，这期帖子就到这里，我们下期不见不散！
帖子信息
最新更新时间：2026年2月2日9时55分