解法一:质因数分解
时间复杂度:$O(nlog(n))$
$n! = C \times 2^a \times 5^b,a > b \to \frac{n!}{10^b} = C \times 2^{a - b}$
由此答案为:$\frac{n!}{10^b} \% 10 = C \times 2^{a - b} \% 10$,避免溢出,需每次对 $C$ 取模。
C++ 代码
#include <iostream>
using namespace std;
int n;
int main()
{
cin >> n;
int c = 1, d2 = 0, d5 = 0;
for (int i = 1; i <= n; ++i) {
int x = i;
while (x % 2 == 0) d2++, x /= 2;
while (x % 5 == 0) d5++, x /= 5;
c = c * x % 10;
}
for (int i = 1; i <= d2 - d5; ++i) c = c * 2 % 10;
cout << c << endl;
return 0;
}
解法二:找规律
时间复杂度:$O(n)$
1! = 1 1
2! = 2 2
3! = 6 6
4! = 24 4
5! = 120 2
6! = 720 2
7! = 5040 4
8! = 40320 2
9! = 362880 8
由此是可以看出一些规律的,每次只取末尾非 $0$ 的最后一位,与下一个数相乘,再取末尾最后一位非 $0$ 即为该数阶乘下的答案,但,例如 $13!$ 是不满足答案的。
依据 $0\le N \le 1000$,每次取末尾非 $0$ 的后三位是成立的。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int main()
{
cin >> n;
int res = 1;
for (int i = 1; i <= n; ++i) {
res = res * i;
while (res % 10 == 0) res /= 10;
res = res % 1000;
}
while (res % 10 == 0) res /= 10;
cout << res % 10 << endl;
return 0;
}
为啥取三位就可以呢,蒙蔽了,还有就是
while (!(res % 10))//去除末尾 0 { res = res / 10; }
可以提到for外吗,不可以的话为什么....
提到
for
外面会 TLE,因为res
会取到 $0$。为什么取三位就可以,取一位或两位又不行?,这里是需要依据 $N$ 的范围来看的,比如只取一位,$12 \times 15 == 180$,最后一位为 $8$ ,但只取一位就是 $3$,而取三位就是为了避免该类情况。