A25281. nonzero问题描述小明最近对阶乘很感兴趣，但是阶乘增长的太快了。如13!就必须用32位整数类型来存储，70!即使浮点数也存不下。小明想知道阶乘最后面的非零位是多少。例如：5!=1*2*3*4*5=120，所以5!最后面的非零位是2。7!=1*2*3*4*5*6*7=5040，所以7!最后面的非零位是4。输入说明一行，一个整数N（N≤1000）。输出说明一行，输出N!最后面的非零位。样例输入7…
填空题
中等
知识点
题目描述
nonzero
问题描述
小明最近对阶乘很感兴趣，但是阶乘增长的太快了。如13!就必须用32位整数类型来存储，70!即使浮点数也存不下。小明想知道阶乘最后面的非零位是多少。
例如：5!=1*2*3*4*5=120，所以5!最后面的非零位是2。
7!=1*2*3*4*5*6*7=5040，所以7!最后面的非零位是4。
输入说明
一行，一个整数N（N≤1000）。
输出说明
一行，输出N!最后面的非零位。
样例输入
7样例输出
4参考答案
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int lastdigit = 1; // 分离出所有的2和5之后的最后一位，一定不会为0。
int cnt2 = 0; // 统计有多少个2因子
for(int i=1; i<=n; i++)
{
int t=i;
while(t%2 == 0)
cnt2++, t /= 2;
while(t%5 == 0)
cnt2--, t /= 5; // 2*5=10，因此一个2因子和一个5因子抵消
lastdigit *= t;
lastdigit %= 10; // 只需保留最后一位
}
// 确定最后位（非0位）的数字
while(cnt2--)
{
lastdigit *= 2; // 整体乘2
lastdigit %= 10; // 只取最低位（防爆）
}
cout<<lastdigit<<endl;
return 0;
}答案解析
直接维护最后一个非零为当然是错误的做法。但如果分离出所有的2和5的因子，剩下的最后一个非零数就不可能再变成0。时间复杂度：O(n)
上一题
下一题