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/-/ow00hepNjeMJ. 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.
