AcWing 888. 求组合数 IV python3
原题链接
简单
作者:
xanxus1111
,
2020-06-22 11:11:31
,
所有人可见
,
阅读 602
# 1.分解质因数
# 2.高精度乘法
N = 5010
primes, cnt = [0] * N, 0
st = [False] * N
sum = [0]* N
def get_primes(n):
global cnt
for i in range(2,n+1):
if not st[i]:
primes[cnt] = i
cnt += 1
j = 0
while primes[j] <= n // i :
st[primes[j]*i] = True
if i % primes[j] == 0: break
j +=1
#求n包含p的个数
def get(n,p):
res = 0
while n:
res += n // p
n //= p
return res
#高精度乘法
def mul(a,b):
c = []
t = 0
for i in range(len(a)):
t += a[i] * b
c.append(t%10)
t //= 10
while t:
c.append(t%10)
t//=10
return c
if __name__ == '__main__':
a,b = map(int,input().split())
get_primes(a)
#枚举每个质数的次数
for i in range(cnt):
p = primes[i]
sum[i] = get(a,p) - get(b,p) - get(a-b,p)
res = [1]
for i in range(cnt):
for j in range(sum[i]):
res = mul(res,primes[i])
for i in range(len(res)-1,-1,-1):
print(res[i],end="")