73
HDU 3123 大数阶乘取模
题意：Output the answer of (0! + 1! + 2! + 3! + 4! + ... + n!)%m.
这题想难了，暴力就行的东西我竟然素因子分解那么做了，这么做素数的时候比暴力慢，不是素数的时候我也不知道快不快。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 1100
bool isprime[maxn];
int prime[maxn],nprime;
void getprime()
{
memset(isprime,1,sizeof(isprime));
long long i,j;
nprime=0;
for(i=2; i<maxn; i++)
if(isprime[i])
{
prime[nprime++]=i;
for(j=i*i; j<maxn; j+=i)
isprime[j]=0;
}
}
int factor[35],tol;
void findfac(int m)
{
int d=m;
tol=0;
for(int i=0; prime[i]*prime[i]<=m; i++)
while(d%prime[i]==0) factor[tol++]=prime[i],d/=prime[i];
if(d>1) factor[tol++]=d;
}
char c[105];
int n,m;
int getn()
{
int len=strlen(c),ans=0;
for(int i=0; i<len; i++)
{
ans=ans*10+c[i]-'0';
if(ans>=m)
return m-1;
}
return ans;
}
int main()
{
int t;
long long yl;
getprime();
scanf("%d",&t);
while(t--)
{
scanf("%s%d",c,&m);
yl=getn();
findfac(m);
int d1=yl;
for(int i=2; i<=yl; i++)
{
int d2=i;
for(int j=0; j<tol; j++)
if(d2%factor[j]==0&&factor[j]!=1)
d2/=factor[j],d1/=factor[j],factor[j]=1;
if(d1==1)
{
yl=i;
break;
}
}
long long ans=1,jc=1;
for(long long i=1; i<=yl; i++)
jc=(jc*i)%m,ans=(ans+jc)%m;
ans=(ans%m+m)%m;
printf("%I64d\n",ans);
}
return 0;
}
最后更新：2017-04-03 16:48:47