@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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
