寒假打卡——AcWing1381. 阶乘
2021-01-24
1381. 阶乘
题意
N 的阶乘(记作 N!)是指从 1 到 N(包括 1 和 N)的所有整数的乘积。
阶乘运算的结果往往都非常的大。
现在,给定数字 N,请你求出 N!的最右边的非零数字是多少。
例如 5!=1×2×3×4×5=120所以 5!的最右边的非零数字是 2。
思路
因式分解:
思路很简单:对原阶乘式子进行因式分解,即质因子的个数,容易发现末尾为0的肯定是2*5得到的,
我们将a[2]和a[5]均减掉min(a[2],a[5]),这样按质因子算的阶乘的时候只用保留最右边一个数即可,末尾不会出现0的情况了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) {
int x=i;
for(int j=2;j<=x;j++) {
if(x%j==0) {
int cnt=0;
while(x%j==0) {
cnt++;
x/=j;
}
a[j]+=cnt;
}
}
if(x) a[x]++;
}
int temp=min(a[2],a[5]);
a[2]-=temp;
a[5]-=temp;
/*
for(int i=2;i<=10;i++) {
cout<<a[i]<<' ';
}
puts("");
*/
long long int k=1;
for(int i=2;i<=n;i++) {
long long int x=1;
while(a[i]) {
x*=i;
x%=10;
a[i]--;
}
k*=x;
k%=10;
}
cout<<k<<'\n';
return 0;
}