N 的阶乘(记作 N!)是指从 1 到 N(包括 1 和 N)的所有整数的乘积。
阶乘运算的结果往往都非常的大。
现在,给定数字 N,请你求出 N! 的最右边的非零数字是多少。
例如 5!=1×2×3×4×5=120,所以 5! 的最右边的非零数字是 2。
输入格式
共一行,包含一个整数 N。
输出格式
输出一个整数,表示 N! 的最右边的非零数字。
数据范围
1≤N≤1000
输入样例:
7
输出样例:
4
#include<bits/stdc++.h>
using namespace std;
//n! = 2^x * 5^y * p = S
//即求 (S/10^k)%10 k = min(x,y)
int n,ans = 1,d2,d5;
//ans储存答案 d2表示n!中2^d2 d5表示n!中5^d5
int main()
{
cin>>n;
for(int i = 1; i <= n; i++){
int x = i;
while(x % 2 == 0) x /= 2, d2++;
while(x % 5 == 0) x /= 5, d5++;
ans = ans*x%10;
}
int k = min(d2,d5);
for(int i = 1; i <= d2 - k; i++) ans = ans*2%10;
for(int i = 1; i <= d5 - k; i++) ans = ans*2%10;
cout<<ans<<endl;
return 0;
}