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.

**Constraints:**
n is less than 10

^{500}.
P is less than 10

^{9}.
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.

Thanks

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteTotally, the actual write-up is really the very best in that will worthwhile matter. I really fit in jointly with your results and certainly am going to keenly seem to be toward your own upcoming improvements. Just telling many http://awriter.org/iwriteessays-com-review/ thanks could not only be sufficient, for your exceptional readability as part of your composing.I'll use this information to provide term papers for my friends.

ReplyDelete