wilson's theorm + fermat's theorem :---BORING Factorials

       
                           SPOJ :- BORING - Boring Factorials

 According to wilson's theorem 
 for prime numbers  ((n-1)!) mod n = n-1

In the question Boring factorials
we hv to find :---   N! mod P

(1*2*..*(n-1)*(n)*..*(p-1) )mod P= P-1  (wilson's)

(1*2*..*(n-1)*(n) )mod P  (this is the question)

=(P-1) / ((n+1)*(n+2)*..*(P-2)*(P-1)) mod P






#include<bits/stdc++.h>

using namespace std;

#define ll long long int


long long int read_int(){
char r;
bool start=false,neg=false;
long long int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}


ll power(ll a,ll b,ll mod)
{
ll ans=1;
while(b)
{
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod;
b/=2;
}
return ans;
}



int main()
{
 int t;
 //cin>>t;
 scanf("%lld",&t);

 while(t--)
 {

   long long int n,p,i,j,k,l,a=1;
   //cin>>n>>p;
   scanf("%lld%lld",&n,&p);

   if(n>=p)
   {
      // cout<<0<<endl;
       long long int y=0;
       printf("%lld\n",y);
       continue;
   }

   a=(p-1);
   for(i=n+1;i<p;i++)
   {
    a=((a%p)*(power(i,p-2,p)%p))%p;
    a=a%p;
   }

 // cout<<a<<endl;
  printf("%lld\n",a);


 }
return 0;
}

Comments

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.