y总说,写算法题不能想当然,要把每一步都弄清楚。。。所以我一开始就想当然的WA了
先看一下前20个数字的阶乘是多少
不难发现,去掉末尾所有的零然后取个位数就是答案了
- 去掉末尾所有的零的方法是 有
k
个零,就将该数除以 $10^k$ 次方即可,例如 $\frac{12000}{10^3} = 12$ - 对任意一个正整数取个位数的方法是将它对十取余 例如
567 % 10 = 7
要求的答案为 $\frac{n!}{10^k}$ mod 10(n为输入样例)
k怎么求呢?
k代表的是 n! 末尾零的个数,也就是除10的次数,即 $10^k$
因为 n! = 1 x 2 x 3 x…x n,又因为10的因数为2 和 5
我们从每一项乘数中 抽离出 2 和 5
假设抽离出了a个2,b个5,即 $2^a5^b$,那么10(k)的个数为 min(a, b)
例如 $2^45^2$ => $2^22^25^2$ => $2^2(2 * 5)^2$ =>
4 * 10 * 10
所以k的个数为2
怎么样分离出因数 2 和 5呢?
由于 n! 是一个合数(除质数外的数),所以可对其进行质因数分解
n! = $2^a5^b$ $p_1^{a1}p_2^{a2}p_3^{a3}…p_m^{am}$
设 min(a, b) = c
则$\frac{n!}{10^k}$ = $2^{a - c}5^{b - c}$ $p_1^{a1}p_2^{a2}p_3^{a3}…p_m^{am}$
则$\frac{n!}{10^k}$ mod 10 = ( $2^{a - c}5^{b - c}$ $p_1^{a1}p_2^{a2}p_3^{a3}…p_m^{am}$ )mod 10
因为 (a * b) % p = (a % p * b % p) % p
且除2和5之外的因数包括在1x2x3…x n之中
所以我们只需要枚举乘数,求出 2 和 5 两个因数的个数,边乘边取10的余即可求解
AC代码
#include <iostream>
using namespace std;
int main(){
int n;
scanf("%d", &n);
int res = 1;
int d2 = 0, d5 = 0; // 定义2和5的数量
for(int i = 1; i <= n; ++i){
int t = i;
while(t % 2 == 0) t /= 2, d2 ++;
while(t % 5 == 0) t /= 5, d5 ++;
res = res * t % 10;
}
// 求出k 并将剩余部分乘上
int k = min(d2, d5);
if(k == d2) {
for(int i = 0; i < d5 - k; ++ i) res = res * 5 % 10;
}else {
for(int i = 0; i < d2 - k; ++ i) res = res * 2 % 10;
}
cout << res << endl;
return 0;
}