题目
题目链接
题解
思维。
既然它要取最后一个非零位,那么我们第一时间想到的肯定是取模,只用保留后几位就行了,但是保留后几位呢,对10
的多少次方取模合适呢?
数据量是100
,那么估算一下存在多少个零,能导致末尾零的出现无非就是乘以十的倍数或者最后一个非零位是2
的数乘以最后一个非零位是5
的数吧,这些情况大概会导致出现十个零以上啊,你说开longlong
,十个零是只算十的倍数的情况,加上2 5
的情况必然超longlong
。
因此,这里用了点小技巧,既然末尾出现零了,那么再乘以别的数末尾还是零,存下来也没意义,不如我们每次乘完一个数,就消去末尾全部的零,这样我们最后得到的数只要对十进行取模就是答案了。
代码
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e5; // 开1000也行,但是100不行
int n, ans = 1;
int main()
{
cin>>n;
for(int i = 1;i <= n;i ++) {
ans = ans*i % MOD; // 乘法,取模
while(ans%10 == 0) ans/=10; // 去掉尾部的0
}
cout << ans % 10 << endl; // 取最后一位非零数
return 0;
}