5

私はこれについて多くの作業を行いましたが、より大きなテストケースの答えを見つけることができませんでした

問題文

数学では、二項係数は、二項定理の係数として発生する正の整数のファミリーです。C（n、k）は、n個の異なるオブジェクトからk個のオブジェクトを選択する方法の数を示します。

ただし、nとkが大きすぎる場合は、素数Pによるモジュロ演算後にそれらを保存することがよくあります。Pによるモジュロ後にnの二項係数が0になる数を計算してください。

入力

最初の入力は、テストケースの数である整数Tです。

次の各T行には、nと素数Pの2つの整数が含まれています。

出力

各テストケースについて、出力行には\ 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)-pの素因数分解におけるnCrの指数-はpnCr

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)で、はの基本p表現の桁の合計ですk。したがって

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との加算にキャリーインベースがない場合に限り、素数で割り切れません。prn-rp

それはまさにその時だからσ_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

したがって、3で割り切れない(1+1)*(0+1)*(1+1) = 4係数と3で割り切れる係数があります。10Cr10 + 1 - 4 = 7

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を試して、私が話していることを確認してください。計算では、10 C r mod 3 = 0の場合にrの3つの値が返されますが、実際には7つあります。

于 2012-08-09T05:35:30.723 に答える