@Ankit: I haven't written code for this problem, but here is how I would do it. You are given values of n and P, with n being up to a 500-digit number (e.g., stored in an array, with say 9 digits of the number stored in each of up to 112 (500/9 rounded up) integers and P fitting in one integer. Write n in base P. You do this using long division to divide n by P. Just simulate what you do when you use long division by hand. The remainder is the low-order base-P digit of n. Repeat the process on the quotient to get successive base-P digits of n, until the quotient is zero. What you now have computed is the m_i of the Wikipedia article. Note the "Consequence" in the article, that the binomial coefficient is divisible by the prime if any n_i is greater than the corresponding m_i. Note that the binomial coefficient is divisible by the prime if and only if the binomial coefficient is zero modulo the prime. So how many possible k <= n are there for which any of the n_i (the base-P digits of k) exceed the corresponding m_i? It is easier to calculate the number of k with all n_i <= m_i: this is just one less than the product all of the (m_i + 1). So calculate this number in base-P arithmetic. Then subtract it from the base-P representation of n to get the base-P representation of the answer. Note that we never calculated any binomial coefficients to determine the answer! Now convert the base-P representation of the answer back to base 10 to the 9th power and print it out. You will have to use long long int (64 bits) for some of the calculations, although the base-P digits of n and P will fit in ordinary 32-bit ints. Dave On Sunday, August 26, 2012 6:56:19 PM UTC-5, Ankit Singh wrote:
> @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 <dave_an...@juno.com > <javascript:>>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 algo...@googlegroups.com<javascript:> >> . >> To unsubscribe from this group, send email to >> algogeeks+...@googlegroups.com <javascript:>. >> 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/1fxRn6HSPaMJ. 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.
