Dementia Problem MULFACT

general
,
1

What is wrong with my solution. I can’t figure out what was wrong.

/*	ashish1610	*/
#include<bits/stdc++.h>
using namespace std;
#define mod 329885391853
/*	fast input	*/
inline void inp(long long int &n) 
{
	  n=0;
  register long long int ch=getchar_unlocked();
  long long int sign=1;
	  while(ch<'0'||ch>'9')
  {
	if(ch=='-')
		sign=-1; 
	ch=getchar_unlocked();
}
	while(ch>='0'&&ch<='9')
        n=(n<<3)+(n<<1)+ch-'0',ch=getchar_unlocked();
	n=n*sign;
  }
  int main() 
 {
int t;
cin>>t;
while(t--)
{
	long long int n;
	inp(n);
	if(n>=999983)
	{
		cout<<0<<endl;
	}
	else
	{
		long long int ans=1,fact=1;
		for(long long int i=1;i<=n;++i)
		{
			fact=((fact%mod)*(i%mod))%mod;
			ans=((ans%mod)*(fact%mod))%mod;
		}
		cout<<ans%mod<<endl;
	}
}
return 0;

}

2

since modulo is large so if u will use simple multiplication it will cause overflow.
to avoid overflow u can use the function given in the topcoder link http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

1 Like
3

Sorry to community. I got the mistake.

4

for n=10^5 your solution is giving negative value … so instead of long long use unsigned long long …

5

we can use one logic to avoid overflows here.
to find ab mod m and ab is out of range, just find a number c such that a.c and a.b/care in the range eg here i took it to be 1000000
ab = a*((b/c)c+b%c) = (((ac)mod m )(b/c))mod m +a(b%c)mod m.