我在这方面做了很多工作,但找不到更大测试用例的答案
问题陈述
在数学中,二项式系数是作为二项式定理中的系数出现的一族正整数。 C(n,k)表示从n个不同对象中选择k个对象的方法数。
但是当n和k过大时,我们往往对质数P取模后保存。请计算n对P取模后有多少个二项式系数为0。
输入
输入的第一个是整数T,测试用例的数量。
接下来的 T 行中的每一行都包含 2 个整数,n 和素数 P。
输出
对于每个测试用例,输出一行包含\tbinom nks (0<=k<=n) 的个数,每个 nks 被 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
最佳答案
您可以从另一端看:有多少 nCr
不能被 p
整除?有一个相当简单的公式。
预赛:
二项式系数 nCr
由下式给出
nCr = n! / (r! * (n-r)!)
因此 nCr
中 p
的重数 v_p(nCr)
- 质数中 p
的指数nCr
的因式分解 - 是
v_p(nCr) = v_p(n!) - v_p(r!) - v_p((n-r)!)
n!
中 p
的重数很容易确定,一种众所周知的计算方法是
v_p(n!) = ∑ floor(n/p^k)
k > 0
如果考虑 n
的基数 p
扩展,您可以看到这个公式,您可以看到
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(a + b) = σ_p(a) + σ_p(b)
的时候。当 a
和 b
的相应数字之和(如果已经为较低有效数字产生进位,则可能加上进位)是加法中的进位>= p
,则和中对应的数字减p
,下一位高位加1,数字和减p - 1
。
我们有一个无进位加法n = r + (n-r)
in base p
if for each digit d_k
in n
的base-p
展开,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
有 n+1
(非零)二项式系数 nCr
,因此(非零)二项式系数的数量 nCr
被 p
整除是
m
n + 1 - ∏ (d_k + 1)
k=0
用 n
的上述基础 p
扩展。
使用 Michael's example n = 10
, p = 3
,
10 = 1*3^0 + 0*3^1 + 1*3^2
所以有 (1+1)*(0+1)*(1+1) = 4
系数 10Cr
不能被 3 和 10 整除+ 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)
关于python - 求二项式系数模质数,面试街头挑战,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11867162/