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("%I64dn",ans);
    }
    return 0;
}