What exactly is the difference between the following two solutions? Solution 2 is getting accepted but not solution 1. From what I can tell they follow the same logic and gave indentical results for the cases I have tested.
Solution 1 :
#include <iostream>
using namespace std;
long ModExp(long B, long N, long P)
{
long Ans = 1;
while (N > 0)
{
if (N % 2 == 1)
Ans = (Ans * B) % P;
B = (B * B) % P;
N /= 2;
}
return Ans;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int N, P;
cin >> N >> P;
if (N >= P)
cout << 0 << endl;
else if (N == P-1)
cout << P-1 << endl;
else
{
long Ans = P-1;
for (int I = N + 1; I < P; I++)
{
Ans = (Ans * ModExp(I, P-2, P)) % P;
}
cout << Ans << endl;
}
}
return 0;
}
Solution 2 :
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL ModEx(LL a,LL b,LL m) /* Function used to do MODULAR EXPONENTIATION a^b mod m */
{
LL x=1,y=a;
while(b>0)
{
if(b & 1)
x=(x*y)%m;
y=(y*y)%m;
b>>=1;
}
return x;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
LL n,p,i,result=-1,temp;
scanf("%lld%lld",&n,&p);
if(n>=p) // In this case, P would be present as
//multiple, hence %p will lead to zero
{
printf("0\n");
continue;
}
for(i=n+1;i<p;i++)
{
temp=ModEx(i,p-2,p); // Function used to calculate
//inverse of i
result=(result*temp)%p;
}
printf("%lld\n",p+result);
}
return 0;
}