I am happy cause only one problem and i will be done solving interviewstreet mathematical problems. After solving the Binomial Coefficients problem i think i have something useful to share with you.
In this problem you are given two number N and P, where P is a prime number. You are requested to find how many binomial coefficients of n become to 0 after modulo by P.
So the output should be the number of s (0<=k<=n) each of which after modulo operation by P is 0.
I hear you saying its an easy problem, but you won't say that after knowing about the input constraints.
n is less than 10500.
P is less than 109.
For such large number i will use Java to solve this problem, thanks to the BigInteger Class in java. After doing some search i found that there is a theorem called Lucas' Theorem which is as follows:
Given n, k, and prime p, binomial (n,k) is divisible by p if and only if at least one of the base p digits of k is larger than the corresponding digit of m (also base p digit).
So to solve this problem we need to find the base P representation of n, and counting how many numbers (R) that have all digits (in base P) less than the corresponding digit in n.
1. We have k is between 0 and n, so we have (n+1) numbers to check with n.
2. Now need to find R.
Now if n in base P is as follows: abc...
Then we need to get all numbers that have:
1. First digit is 0, 1, 2, .... a-1
2. Second digit is 0, 1, 2, .... b-1
3. Third digit is 0, 1, 2, ...., c-1
Obviously R = (a+1)*(b+1)*(c+1).
So we have (n+1) total numbers, subtracting R, then the result would be n+1-R.