@dave: Can u Please elaborate your idea?? I didn't understand lucas theorem and in that theorem, i see too much calculation and here we have to deal with testcases upto 100 and each testcase containing n in range of 10500.
On Mon, Aug 27, 2012 at 4:02 AM, Dave <[email protected]> wrote: > @Ankit: Apply Lucas' Theorem, which you can find written up in Wikipedia. > > Dave > > On Sunday, August 26, 2012 3:57:18 PM UTC-5, Ankit Singh wrote: > >> In mathematics, *binomial coefficients* are a family of positive >> integers that occur as coefficients in the binomial theorem. [image: >> \tbinom nk] denotes the number of ways of choosing k objects from n >> different objects. >> >> However when n and k are too large, we often save them after modulo >> operation by a prime number P. Please calculate how many binomial >> coefficients of n become to 0 after modulo by P. >> >> *Input* >> >> The first of input is an integer T , the number of test cases. >> >> Each of the following T lines contains 2 integers, n and prime P. >> >> *Output* >> >> For each test case, output a line contains the number of [image: \tbinom >> nk]s (0<=k<=n) each of which after modulo operation by P is 0. >> >> *Sample Input* >> >> 3 >> >> 2 2 >> >> 3 2 >> >> 4 3 >> >> *Sample Output* >> >> 1 >> >> 0 >> >> 1 >> >> *Constraints:* >> >> T is less than 100 >> >> n is less than 10500. >> P is less than 109. >> >> >> >> >> I Have applied a logic that if any binomial coefficient can be written as >> n!/(n-k)!k! so if (n/p)>((n-k)/p+k/p) so that coefficient will be >> divisiblr by prime number p. but the problem is range of is so large so if >> i give an input of that much range it will take more then 15 min . although >> complexity of my code is O(n/2) but my program keep on running because of >> very high range of input. Can anyone help me in this please?? >> >> Thank you >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/aLFSGCkdtmsJ. > > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
