寻找二项式有效模素数，采访街头挑战

Question

我在这方面做了很多工作，但找不到更大测试用例的答案

在数学中，二项式系数是在二项式定理中作为系数出现的一系列正整数。C（n，k）表示从n个不同对象中选择k个对象的方法的数量。

然而，当n和k太大时，我们通常在通过素数P进行模运算后保存它们。请计算n在通过P模运算后有多少二项式系数变为0。

第一个输入是一个整数T，即测试用例的数量。

以下每一条T线都包含2个整数，n和素数P。

对于每个测试用例，输出一行包含\tbinom NK的数量（0

3
2 2
3 2
4 3

1
0
1

• T小于100
• n小于10^500.
• P小于10^9.

我用二项式系数中的余数定理完成了这项工作

         #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*(b-t)
           result.append(j)
        for i in range(N):
           print result[i]

上述条件对于较小的数是满足的

样本测试用例

n=18794630774601781017426704938831913907435978269230795331996679039914346399046250032752062869664969026409717407691286722246746310051635510258172010540705068068062855577739018819952185016092141574603857575517389685582264304970416367431857952154025664646411119006572746826261266043520236417734545427770334990400306682949871260040370515062243982543271073443613028133844603853807066311479739789908983610180228625059956919930500586048799830730348503994503184106117058

p=177080341

我的输出是

2296508200406431043037217853758906667313789305876262916681342008001095232916608835588093082038358975456171743147798282523487485386336553910277635713985851142371010771392102277877640275384064735398164190968282400640398659343189330639672472613876688344609533340662724884373078840434716174167873375700938597411315754265893890741730938202927739246687866166994143001482839656000969674716959277820008958538229366474207686428750934149471409162993083541475267772950721250234982686128039722553219836725588488

预期产出为

18794630773460178101742635959946548665553041135822283621364103266511586625905046107130878283695016799933475657268010472422112556606280021574002866456544310584537519228161286450725015989697306855581489155139723025246780552510467580791551824827637581156204185887378181074365453150481221030356075255000460025095384537510111086396988416046942446776262625161326885418101128327416784858513888616089287333560469336094431461981368825028447505354473183546488856594449627370807707483671453574074503184106117059

Answer 1

你的公式失效了。

你在计算l*（p-t-1）。

如果有p^2，p^3等的因子，这个公式就不起作用了

对于较小的数字，尝试n=10，p=3来了解我在说什么。你的计算将返回3个r值，其中10 C r mod 3=0，但实际上有7个。

Answer 2

你可以从另一端看：有多少nCr不能被p整除？这有一个相当简单的公式。

二项式系数nCr由下式给出

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

因此，在nCr中p的多重性v_p（nCr）——在nCr的素因式分解中p的指数是

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

pinn 可以很容易地确定，一个众所周知的计算方法是

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

如果你考虑到p扩展的n，看看这个公式，你会发现

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

其中，σ_p（k）是k表示的基p的位数之和。因此

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

nCr不可被素数p整除当且仅当r和n-r的加法没有进位基p。

因为这正是当σp（ab）=σp（a）σp（b）时。当A和b的相应数字之和（如果已经为较低有效数字生成进位，则可能加上进位）为

在basep中，我们有一个无进位加法n=r（n-r），如果对于n的base-p展开中的每个数字d_k，则的相应数字>r小于或等于d_k。r的数字的允许选择是独立的，因此总数是单个数字的选择计数的乘积。

不能被素数p整除的nCr数是

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

其中d_k是n的基p展开中的数字，

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

由于给定的n存在n1（非零）二项式系数nCr，因此可被p整除的（非零）二项式系数的数量为

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

用上面的p扩展n。

使用Michael的例子n=10，p=3，

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

因此有（11）*（01）*（11）=4系数10Cr不可被3整除和101-4=7可被3整除。

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