5

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

问题陈述

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

但是当n和k太大的时候，我们经常在对一个素数P进行模运算后保存。请计算n有多少个二项式系数在对P进行模运算后变为0。

输入

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

以下 T 行中的每一行都包含 2 个整数，n 和素数 P。

输出

对于每个测试用例，输出一行包含 \tbinom nks (0<=k<=n) 的数量，每个在 P 的模运算后为 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=18794630773460178101742670493883191390743597826923079533199667903991430393463990462500322752062869664969026409174076912867222446746310051635510258172105034070506806228555577773599018819952185016092141574603857551738968553782672643049704163674318579695215402562964641111900657274032612661770435202254364177910753450214277150377049334509093906874400306682949871260040370515062243982543271073443613028133844603853807066311479739789908983610180228625059956919930500586048799830730348503994503184106117058

p= 177080341

我的输出是

2296508200406431043037217853758906667313789305876262916681342008001095232916608835588093082038358975456171743147798282523487485386336553910277635713985851142371010771392102277877640275384064735398164190968282400640398659343189330639672472613876688344609533340662724884373078840434716174167873375700938597411315754265893890741730938202927739246687866166994143001482839656000969674716959277820008958538229366474207686428750934149471409162993083541475267772950721250234982686128039722553219836725588488

预期输出是

18794630773460178101742635959946548665553041135822283621364103266511586625905046107130878283695016799933475657268010472422112556606280021574002866456544310584537519228161286450725015989697306855581489155139723025246780552510467580791551824827637581156204185887378181074365453150481221030356075255000460025095384537510111086396988416046942446776262625161326885418101128327416784858513888616089287333560469336094431461981368825028447505354473183546488856594449627370807707483671453574074503184106117059

4

2 回答 2

15

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

预赛：

二项式系数nCr由下式给出

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

所以 in 的多重性v_p(nCr)- in 的主要因式分解的指数- 是pnCrpnCr

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

pin的重数n!可以很容易地确定，一种众所周知的计算方法是

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

如果考虑这个公式的基数p扩展n，你可以看到

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

其中是 的基本表示σ_p(k)的数字之和。因此pk

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(a + b) = σ_p(a) + σ_p(b). 当 和 的对应数字之a和b（如果已经为较低有效数字产生进位，则可能加上进位）>= p为p数字加 1，数字和减少p - 1.

如果对于 的基数扩展中的每个数字，对应的数字小于或等于 ，我们n = r + (n-r)在基数中有一个无进位加法。的数字的允许选择是独立的，因此总数是单个数字的选择计数的乘积。pd_knprd_kr

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

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

其中是的基本扩展d_k中的数字，np

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

由于给定的 有n+1（非零）二项式系数，因此可被整除的（非零）二项式系数的数量为nCrnnCrp

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

与上述基数p展开n。

使用迈克尔的 例子n = 10，，p = 3

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

所以有些(1+1)*(0+1)*(1+1) = 4系数10Cr不能被 310 + 1 - 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)
于 2012-08-10T21:46:13.957 回答
0

你的公式已经关闭了。

您正在计算 l * (p - t - 1)。

如果存在 p^2、p^3 等因子，则此公式不起作用。当 l > p 时（如果 m > p 也可能）会发生这种情况。

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

于 2012-08-09T05:35:30.723 回答