### div24ever's blog

By div24ever, history, 4 years ago, ,

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



• 0

 » 4 years ago, # |   0 Can you prove that: n >= 587117 -> ans = 0 ???
•  » » 4 years ago, # ^ |   +1 Yes because 109546051211 = 186583 * 587117. For n >= 587117, modulo will give answer 0.
•  » » 4 years ago, # ^ |   0 My code is less than 1.0 time http://ideone.com/Pv3efT
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Thanks! Computing factorial simultaneously in the loop gave AC in 0.71 time and i reduced memory used from 12M to 3.3M!
•  » » 4 years ago, # ^ |   0 How can we calculate such a number like 587117? Or do we have to know it?
•  » » » 4 years ago, # ^ |   0