python - 连续数可被质数除以帕斯卡三角形的数字数

如何找到pascal三角形的给定行号中可被给定行号和素数的素数整除的数的总数
我在python中使用以下代码

def factorial(x):
    result = 1
    for i in xrange(1,x+1):
        result *= i
    return result

def combination(n,r):
    return factorial(n)/(factorial(n-r)*factorial(r))

p = input()
cnt = 0
for i in range(0,n+1):
    if((combination(n,i)%p)==0):
        cnt += 1
print cnt

但是给定的代码对于大的数字来说需要很长时间。
你能给我推荐一个更好的算法吗。

最佳答案

Luca's theorem的一个推论是，不可被素数p整除的二项式系数C（n，k）的个数是
(a₁+1)⋅(a₂+1)⋅...⋅(a+1)，其中ai是p元数字系统中n的第i位。
例子：
p=3，n=7dec=213
结果=（2+1）（1+1）=6
帕斯卡三角形的第7行是1 7 21 35 35 21 7 1，它包含6个不可被3整除的系数，其余两个可被3整除。