题目描述
N 的阶乘(记作 N!)是指从 1 到 N(包括 1 和 N)的所有整数的乘积。
阶乘运算的结果往往都非常的大。
现在,给定数字 N,请你求出 N! 的最右边的非零数字是多少。
例如 5!=1×2×3×4×5=120,所以 5! 的最右边的非零数字是 2。
输入格式
共一行,包含一个整数 N。
输出格式
输出一个整数,表示 N! 的最右边的非零数字。
数据范围
1≤N≤1000
输入样例:
7
输出样例:
4
算法1
(数学) $O(n^2)$
1.同余定理,2个数字乘积求余数等于2个数余数乘积之后再求余数的数再取余数
2.质因数分解,一个数可以拆成多个数次幂的乘积,比如2的k次幂乘以5的k次幂....
3.尾巴0的个数只和2和5有关系,有几对2和5
4.取得个位数就是%10;
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int res = 1, d2 = 0, d5 = 0,k;
for (int i = 1; i <= n; i ++ )//从小到大枚举
{
int x = i;
while (x % 2 == 0) x /= 2, d2 ++ ;//如果可以除掉2的话,就除掉记录2的个数
while (x % 5 == 0) x /= 5, d5 ++ ;//如果可以除掉5的话,就除掉记录5的个数
res = res * x % 10;//全部除掉后就给它乘上去就是剩下没有组成10的数
}
k=min(d2,d5);//记录有多少对2和5
for(int i=0;i<d2-k;++i)
{
res=res*2%10;//把多除的2乘回去
}
for(int i=0;i<d5-k;++i)//多除的5乘回去
{
res=res*5%10;
}
cout<<res<<endl;
return 0;
}