My Weblog

Blog about programming and math

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

Advertisements

February 12, 2009 - Posted by | Uncategorized

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: