How to reduce time in Product of factorials SPOJ?

Revision en1, by dush1729, 2015-10-17 11:59:48

I tried to solve FACTMUL and got AC with 4.82 time. There are many submissions with less than 1.0 time. How to do it in less than 1.0 time?

My code

#include<bits/stdc++.h>
unsigned long long mod=109546051211,fact[587117]={0,1,2,6},a[587117]={0,1,2,12},i,j;
unsigned long long mulmod(unsigned long long a,unsigned long long b)
{
    if((a==0)||(b<mod/a)) return (a*b)%mod;
    unsigned long long x=0,y=a%mod;
    while(b>0)
    {
        if(b%2==1) x=(x+y)%mod;
        y=(y*2)%mod;
        b/=2;
    }
    return x%mod;
}
int main()
{
    for(j=2;j<587117;j++)  //Computes and stores factorial
    {                      //of all number till 587116
        if(fact[j]) continue;
        fact[j]=mulmod(j,fact[j-1]);
    }
    unsigned long long n;
    scanf("%llu",&n);
    if(n>=587117) printf("0\n");
    else
    {
        if(a[n]!=0) printf("%llu\n",a[n]); //It will make no difference
        else                               //because test case is 1
        {
            for(i=2;i<=n;i++) a[i]=mulmod(fact[i],a[i-1]);
            printf("%llu\n",a[n]);
        }
    }
    return 0;
}

Tags spoj, factorial, modular arithmetic, modulus

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dush1729 2015-10-17 11:59:48 1245 Initial revision (published)