扩展题
题目描述
N 的阶乘(记作 N!)是指从 1 到 N(包括 1 和 N)的所有整数的乘积。
阶乘运算的结果往往都非常的大。
现在,给定数字 N,请你求出 N! 的最右边的非零数字是多少。
例如 5!=1×2×3×4×5=120,所以 5! 的最右边的非零数字是 2。
输入格式
共一行,包含一个整数 N。
输出格式
输出一个整数,表示 N! 的最右边的非零数字。
数据范围
简单的数学题,在草稿纸上推导,再模拟一下即可
先求n!末尾有多少个0,把这些零去掉(即10^k:k=min(d2,d5);d2表示n!分解因子后2^d2,同理d5表示5 的……)
将n!去掉10^k后,对剩余的部分对10求余即可;
样例
输入样例:
7
输出样例:
4
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int res=1,d2=0,d5=0;
for(int i=1;i<=n;i++){//n!中枚举1~n
int x=i;//设枚举的这位数为x
while(x%2==0)x/=2,d2++;//x中2的因子个数
while(x%5==0)x/=5,d5++;//x中5的因子个数
res=res*x%10;//去掉所有的2,5剩余部分求余
}
int k=min(d2,d5);
for(int i=1;i<=d2-k;i++)res=res*2%10;//去掉10,将剩余的2乘到结果中求余
for(int i=1;i<=d5-k;i++)res=res*5%10;//同理
cout<<res;
return 0;
}
orz