About ncr%p question

#1

sir when i am calculating using ncr%p using fermat theorem and modulo inverse but it always give the zero answer

#2

Yes. you have to do it with fermet theoram and inverse modulo only.
I think you are not taking mod well.
Take mod at every step to avoid overflow.
Please have a look at this code to get idea.

#3

mod is prime number ,so we can cal modulo inverse by power(n,p-2,p)

#4

i am calculating modulo inverse by power(n,p-2,p)

#5

#include<bits/stdc++.h> using namespace std; int power(int x, int y, int p) { int res = 1; x = x % p; while (y > 0) { if (y & 1) res = (resx) % p; y = y>>1; // y = y/2 x = (xx) % p; } return res; } int modInverse(int n, int p) { return power(n, p-2, p); } // Returns nCr % p using Fermat’s little theorem. int nCrModPFermat(int n, int r, int p) { // Base case if (r==0) return 1; int fac[n+1]; fac[0] = 1; for (int i=1 ; i<=n; i++) fac[i] = fac[i-1]i%p; return (fac[n] modInverse(fac[r], p) % p * modInverse(fac[n-r], p) % p) % p; } int main() { int n = 10, r = 2, p = 1000000007; //cout<<power(10,p-2,p)<<endl; cout << "Value of nCr % p is " << nCrModPFermat(n, r, p); return 0; }

#6

Share your code via ide.codingblocks.com with proper indentation and share the link.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.