結果

問題 No.129 お年玉(2)
ユーザー 👑 rin204rin204
提出日時 2022-07-04 13:58:33
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 892 ms / 5,000 ms
コード長 4,010 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 106,636 KB
最終ジャッジ日時 2024-12-14 03:09:19
合計ジャッジ時間 45,852 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

n = int(input())
m = int(input())
n //= 1000
n %= m
from math import gcd
def isprime(n):
if n <= 1:
return False
elif n == 2:
return True
elif n % 2 == 0:
return False
A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
s = 0
d = n - 1
while d % 2 == 0:
s += 1
d >>= 1
for a in A:
if a % n == 0:
return True
x = pow(a, d, n)
if x != 1:
for t in range(s):
if x == n - 1:
break
x = x * x % n
else:
return False
return True
def pollard(n):
if n % 2 == 0:
return 2
if isprime(n):
return n
f = lambda x:(x * x + 1) % n
step = 0
while 1:
step += 1
x = step
y = f(x)
while 1:
p = gcd(y - x + n, n)
if p == 0 or p == n:
break
if p != 1:
return p
x = f(x)
y = f(f(y))
def primefact(n):
if n == 1:
return []
p = pollard(n)
if p == n:
return [p]
left = primefact(p)
right = primefact(n // p)
left += right
return sorted(left)
def modinv(a, MOD):
b = MOD
u = 1
v = 0
while b:
t = a // b
a -= t * b
u -= t * v
a, b = b, a
u, v = v, u
u %= MOD
return u
def Garner(M, R):
if not M:
return 0
m_prod = M[0]
C = R[0]
for m, r in zip(M[1:], R[1:]):
t = (r - C) * modinv(m_prod, m) % m
C += t * m_prod
m_prod *= m
return C
class Combination_Arbitary_sub:
def __init__(self, p, pq):
self.fact = [0] * (pq + 1)
self.invfact = [0] * (pq + 1)
self.fact[0] = 1
self.invfact[0] = 1
for i in range(1, pq + 1):
if i % p == 0:
self.fact[i] = self.fact[i - 1]
else:
self.fact[i] = self.fact[i - 1] * i % pq
self.invfact[i] = modinv(self.fact[i], pq)
class Combination_Arbitary:
def __init__(self, MOD):
self.MOD = MOD
primes = primefact(MOD)
self.le = len(set(primes))
self.p = sorted(set(primes))
self.q = [0] * self.le
self.pq = [1] * self.le
ind = -1
bef = -1
for p in primes:
if p != bef:
bef = p
ind += 1
self.q[ind] += 1
self.pq[ind] *= p
self.fac = [None] * self.le
for i, (p_, pq_) in enumerate(zip(self.p, self.pq)):
self.fac[i] = Combination_Arbitary_sub(p_, pq_)
def C(self, n, k, p, q, pq, fac):
z = n - k
e0 = 0
u = n // p
while u > 0:
e0 += u
u //= p
u = k // p
while u > 0:
e0 -= u
u //= p
u = z // p
while u > 0:
e0 -= u
u //= p
em = 0
u = n // pq
while u > 0:
em += u
u //= p
u = k // pq
while u > 0:
em -= u
u //= p
u = z // pq
while u > 0:
em -= u
u //= p
ret = 1
while n > 0:
ret *= fac.fact[n % pq]
ret %= pq
ret *= fac.invfact[k % pq]
ret %= pq
ret *= fac.invfact[z % pq]
ret %= pq
n //= p
k //= p
z //= p
ret *= pow(p, e0, pq)
ret %= pq
if(not(p == 2 and q >= 3) and em & 1):
ret = -ret % pq
return ret
def nCk(self, n, k):
if n < k or k < 0:
return 0
R = [0] * self.le
for i in range(self.le):
R[i] = self.C(n, k, self.p[i], self.q[i], self.pq[i], self.fac[i])
return Garner(self.pq, R)
Comb = Combination_Arbitary(10 ** 9)
print(Comb.nCk(m, n))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0