【USACO 3.2.1】阶乘

时间:2023-03-08 19:50:09

【描述】

N的阶乘写作N!表示小于等于N的所有正整数的乘积。阶乘会很快的变大,如13!就必须用32位整数类型来存储,70!即使用浮点数也存不下了。你的任务是找到阶乘最后面的非零位。举个例子,5!=1*2*3*4*5=120所以5!的最后面的非零位是2,7!=1*2*3*4*5*6*7=5040,所以最后面的非零位是4。

【格式】

PROGRAM NAME: rect4
INPUT FORMAT:(file rect4.in)

共一行,一个整数不大于4,220的整数N。

OUTPUT FORMAT:(file rect4.out)

共一行,输出N!最后面的非零位。

【分析】

先打素数表,然后分解质因数,再去掉可以产生末尾0的2和5(不是所有二和五,而是他们的最小值),最后在把剩下的乘起来MOD10。

 #include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
const int maxn=;
using namespace std;
int cnt[maxn],vis[maxn];
int prime[maxn];
void built_prime();//打表
void check(int n);
int pow_mod(int num,int t);
int main()
{
int n,i,temp,ans=;
//文件操作
freopen("fact4.in","r",stdin);
freopen("fact4.out","w",stdout);
built_prime();
//printf("1");
scanf("%d",&n);
for (i=;i<=n;i++) check(i);//分解质因数
temp=min(cnt[],cnt[]);
cnt[]-=temp;cnt[]-=temp;
for (i=;i<=prime[];i++)
{
if (cnt[prime[i]]!=)
ans=(ans*pow_mod(prime[i],cnt[prime[i]]))%;//快速幂取模
}
printf("%d",ans%);
return ;
}
int pow_mod(int num,int t)
{
if (t==) return num%;
if (t==) return (num*num)%;
int temp=pow_mod(num,t/);
if (t%==) return (temp*temp)%;
else return (temp*temp*num)%;
}
void built_prime()
{
int i,j;
memset(cnt,,sizeof(cnt));
prime[]=;
for (i=;i<=maxn;i++)
{
if (vis[i]==)
{
prime[++prime[]]=i;
for (j=i;j<=maxn;j+=i) vis[j]=;
}
}
}
void check(int n)
{
int i;
while (n!=)
{
for (i=;i<=prime[];i++)
if (n%prime[i]==) {cnt[prime[i]]++;n=n/prime[i];break;}
}
}