## Binomial Cofficient

The problem is we have to calculate NCK (K chose out of N) modulo some number P.The problem boils down to Lucas Theorem if P is prime. What if P is not prime ? This problem can also be solve with the help of prime factorisation. Here you can look at Lucas theorem (http://en.wikipedia.org/wiki/Lucas’_theorem) .It is quite easy to impliment but problem is how to solve if P is not prime.My implimentation .If you find any bug then kindly let me know.

bool isprime[1000010];

vector V;

long long _mod(long long a,long long b,long long c)

{

long long ret=1;

while(b)

{

if(b&1) ret=ret*a%c;

a=a*a%c;

b/=2;

}

return ret%c;

}

void _precompute()

{

memset(isprime,0,sizeof isprime);

isprime[0]=1,isprime[1]=1;

for(long long i=2LL;i*i<=1000000LL;i++)

if(!isprime[i])

for(long long j=i*i;j<=1000000LL;j+=i)

isprime[j]=1;

for(long long i=2LL;i<=1000000LL;i++)

if(!isprime[i])V.push_back(i);

}

long long NCK(long long N,long long K,long long mod)

{

memset(isprime,0LL,sizeof isprime);

long long ret=1LL;

for(long long i=0LL;V[i]<=N;i++)

{

for(long long j=V[i];j<=N;j*=V[i])

ret=(ret*_mod(V[i],(N/j-K/j-(N-K)/j),mod))%mod;

}

return ret;

}

int main()

{

long long m,n,p;

V.clear();

_precompute();

while(scanf(“%lld%lld%lld”,&n,&m,&p)==3)

printf(“%lld\n”,NCK(n,m,p));

}

No comments yet.

## Leave a Reply