# My Weblog

## 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));
}