题解
解法0:
python暴力操作,看看就行。
fac = 1
for i in range(1, int(input()) + 1): fac *= i
print(str(fac).replace("0", "")[-1])
解法1:
120!
的阶乘远远超出了long long
的范围,不过我们只需要获取最后的非零元素,所以只需要做一下控制,使其控制在1e9
的范围内。
控制的方法有两种:
1. 去掉末尾的0,即不断除10,因为最后的非零位之后的0对答案毫无影响。
2. 对阶乘的结果膜1e9
,由于第一步操作,后续不可能出现连续的9个0,所以我们可以对其进行取模,控制范围
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9;
int main() {
int n;
cin >> n;
long long fac = 1;
for(int i = 1; i <= n; i++) {
fac *= i;
while(!(fac % 10)) fac /= 10;
fac %= MOD;
}
cout << fac % 10 << endl;
return 0;
}
解法二:
我们进行观察,因为0只可能由2的倍数和5的倍数相乘得到,所以在进行乘法的过程中,我们将2和5的倍数给清理掉,这样就保证了不会出现0,然后我们控制其范围,每次相乘取其个位,因为个位肯定是非零元素,十位以后的数字完全没有必要保留下来,最后,我们将多处理的2或者5重新乘回去再取余即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
long long fac = 1;
int tot_2 = 0, tot_5 = 0;
for (int i = 1; i <= n; i ++ )
{
int tmp = i;
while (!(tmp % 2)) tmp /= 2, ++ tot_2; // 清理因子2
while (!(tmp % 5)) tmp /= 5, ++ tot_5 ; // 清理因子5
fac = fac * tmp % 10; //相乘以后取个位
}
// 这里因为2的因子个数远大于5,所以肯定是2多清理了
for (int i = 0; i < tot_2 - tot_5; i ++ ) fac = fac * 2 % 10; // 仍然是只保留个位,也可以防止溢出
cout << fac << endl;
return 0;
}
%%%%
其实解法1的MOD取1000就可以,因为1000以内不存在大于1000的质数,模1000就可以保留所有非2、5对的质因子。
10以内也不存在大于10的质数呀,为什么是1000呢
这里不能MOD 10,因为计算阶乘(包含取MOD)的过程可能会出现0结尾的结果,比如12345结尾就是个0,mod 10之后就一直是0了。
事实上,mod 1000也不行,因为乘到125,比如会出现一个000结尾的数:
这个代码就TLE了
事实上最后一位数并不一定就是最后位决定的,比如16 * 25 = 400和6 * 25 = 150,他们最后一位非0的数就不同。所以这个中途取mod的做法就不对。
强强强
芜湖!
喵嗷!
妙蛙!!!
妙啊!
秒啊!