如果一个一个去乘肯定不现实,一看数据范围最大给到 这样的量级,考虑每次做完将末尾 0 删除得到新的数,开
long long 存取结果,最后对 取模保留进位信息,在
long long 范围内完全可以存取 这个量级的数,所以可以通过,代码如下。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
long long res = 1;
for (int i = 1; i <= n; i++)
{
res *= i;
while (res % 10 == 0)
res /= 10;
res %= 1000000;
}
cout << res % 10 << endl;
return 0;
}
如果你出现一些问题,例如和我一开始一样如果你每次只存取个位数,会造成进位丢失:
| i | i! | 去掉末尾 0 后的数(表示法) | 正确的末尾非 0 数字 | 只保留上一步的末尾非0数字再乘得到的数字 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 2 |
| 3 | 6 | 6 | 6 | 6 |
| 4 | 24 | 24 | 4 | 4 |
| 5 | 120 | 12 | 2 | 2 |
| 6 | 720 | 72 | 2 | 2 |
| 7 | 5040 | 504 | 4 | 4 |
| 8 | 40320 | 4032 | 2 | 2 |
| 9 | 362880 | 36288 | 8 | 8 |
| 10 | 3628800 | 36288 | 8 | 8 |
| 11 | 39916800 | 399168 | 8 | 8 |
| 12 | 479001600 | 4790016 | 6 | 6 |
| 13 | 6227020800 | 62270208 | 8 | 8 |
| 14 | 87178291200 | 871782912 | 2 | 2 |
| 15 | 1307674368000 | 1307674368 | 8 | 3 ← 首次出现分歧 |
注意第 15 行:真实的 15!(去掉末尾零后)是 1307674368,它的右起第一个非零数字是 8。
但你的“每次只保留上一轮的末尾非零数字(单个数字)再乘”策略在第 15 步给出了 3。
为什么会差别?看具体乘法:
-
用完整的去零后的 14!:
871,782,912 × 15 = 13,076,743,680→ 去掉末尾 0 →1,307,674,368→ 末尾非0为8。
这里发生了大量的“进位”(比如871,782,912 × 5 = 4,358,914,560,和 ×10 的部分相加,进位进了低位),导致乘法的低位(最后一位)变成8。 -
但如果你只记
14!的“末尾非零数”2,直接2 × 15 = 30→ 去零 →3。
这只看到了最低位的乘积而完全忽略了上面那个871,782,91*部分产生的进位,所以结果不同。
复杂度有点难算

京公网安备 11010502036488号