Finding binomial sharing modulo a prime number, calling a street conversation

Question

I did a lot of work on this, but could not find an answer for larger test cases

Problem Statement

In mathematics, binomial coefficients are a family of positive integers that are among the coefficients in the binomial theorem. C (n, k) denotes the number of ways to select k objects from n different objects.

However, when n and k are too large, we often save them after working modulo a prime number P. Please calculate how many binomial coefficients n become equal to 0 modulo P.

Enter

The first input is an integer T, the number of test cases.

Each of the next T lines contains 2 integers, n and a prime P.

Output

For each test case, the line output contains the number \ tbinom nks (0 <= k <= n), each of which after the operation modulo P is 0.

Input example

3 2 2 3 2 4 3 

Sample output

 1 0 1 

Limitations:

• T less than 100
• n is less than 10 500.
• P is less than 10 ^ 9.

Decision

i completed this using the remainder theorem in binomial coefficients

  #C(n,m) mod p #n=l*p+t #m=m*p+s #then C(n,r) mod p=0 when (t<s or t=0) inp1 = raw_input() N=int(inp1) result=[] for i in range(N): inp = raw_input() a, b = [long(x) for x in inp.split(' ')] j=0 #n=lp+t t=a%b t=t+1 l=a/b j=l*(bt) result.append(j) for i in range(N): print result[i] 

condition above for small numbers

sample test case

n = 18794630773460178101742670493883191390743597826923079533199667903991430393463990462500322752062869664969026409174076912867222446746310051635510258172105034070506806228555577773599018819952185016092141574603857551738968553782672643049704163674318579695215402562964641111900657274032612661770435202254364177910753450214277150377049334509093906874400306682949871260040370515062243982543271073443613028133844603853807066311479739789908983610180228625059956919930500586048799830730348503994503184106117058

p = 177080341

my conclusion

2296508200406431043037217853758906667313789305876262916681342008001095232916608835588093082038358975456171743147798282523487485386336553910277635713985851142371010771392102277877640275384064735398164190968282400640398659343189330639672472613876688344609533340662724884373078840434716174167873375700938597411315754265893890741730938202927739246687866166994143001482839656000969674716959277820008958538229366474207686428750934149471409162993083541475267772950721250234982686128039722553219836725588488

Expected Result

18794630773460178101742635959946548665553041135822283621364103266511586625905046107130878283695016799933475657268010472422112556606280021574002866456544310584537519228161286450725015989697306855581489155139723025246780552510467580791551824827637581156204185887378181074365453150481221030356075255000460025095384537510111086396988416046942446776262625161326885418101128327416784858513888616089287333560469336094431461981368825028447505354473183546488856594449627370807707483671453574074503184106117059

Answer 1

Your formula is off.

You compute l * (p - t - 1).

This formula does not work if there are factors p ^ 2, p ^ 3, etc. This will happen when l> p (and possibly if m> p too).

For small numbers, try n = 10, p = 3 to see what I'm talking about. Your calculation will return 3 r values, where 10 C r mod 3 = 0, but in fact there are 7.

Answer 2

You can look at it from the other end: How many nCr not divisible by p ? There is a fairly simple formula for this.

Qualifiers:

The binomial coefficient nCr is determined by the expression

 nCr = n! / (r! * (nr)!) 

therefore, the multiplicity v_p(nCr) of p in nCr - an exponent of p in a simple factorization of nCr - is

 v_p(nCr) = v_p(n!) - v_p(r!) - v_p((nr)!) 

The multiplicity of p in n! can be easily determined, a well-known way of calculating it is

 v_p(n!) = ∑ floor(n/p^k) k > 0 

If you look at this formula taking into account the expansion of the base p n , you will see that

 v_p(n!) = (n - σ_p(n)) / (p - 1) 

where σ_p(k) is the sum of the digits of the base representation k . In this way,

 v_p(nCr) = (n - σ_p(n) - r + σ_p(r) - (nr) + σ_p(nr)) / (p - 1) = (σ_p(r) + σ_p(nr) - σ_p(n)) / (p - 1) 

Output:

nCr not divisible by prime p if and only if the addition of r and nr does not have a carrier in the base p .

Because it’s accurate when σ_p(a + b) = σ_p(a) + σ_p(b) . The non-addition in the appendix occurs when the sum of the corresponding digits a and b (plus, possibly, the transfer, if it has already been carried over for less significant digits) is >= p , then the corresponding digit in the sum decreases by p , and the next more significant digit increases by 1 , decreasing the digital sum by p - 1 .

We have a carrier additive n = r + (nr) in the base p if for each digit d_k in the extension n base- p corresponding digit r less than or equal to d_k . The valid choice of digits r is independent, so the total number is the product of the number of samples for individual digits.

The number nCr not divisible by the prime p is

 ND(n,p) = ∏(d_k + 1) 

where d_k are numbers in the extension n base p ,

  m n = ∑ d_k * p^k k=0 

Since there are n+1 (non-zero) binomial coefficients nCr for a given n , the number of (non-zero) binomial coefficients nCr divisible by p is

  m n + 1 - ∏ (d_k + 1) k=0 

with the above base p extension n .

Using Mike's example n = 10 , p = 3 ,

 10 = 1*3^0 + 0*3^1 + 1*3^2 

therefore, there are coefficients (1+1)*(0+1)*(1+1) = 4 10Cr , not divisible by 3 and 10 + 1 - 4 = 7 , divisible by 3.

 def divisibleCoefficients(n,p): m, nondiv = n, 1 while m > 0: nondiv = nondiv * ((m % p) + 1) m = m // p return (n + 1 - nondiv)