div24ever's blog

By div24ever, history, 4 years ago, In English,

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;
}

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you prove that: n >= 587117 -> ans = 0 ???