結果

問題 No.129 お年玉(2)
ユーザー lam6er
提出日時 2025-04-15 21:17:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 76 ms / 5,000 ms
コード長 1,175 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 81,716 KB
実行使用メモリ 75,776 KB
最終ジャッジ日時 2025-04-15 21:24:01
合計ジャッジ時間 4,423 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

def extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    else:
        g, x, y = extended_gcd(b, a % b)
        return (g, y, x - (a // b) * y)

def crt(a1, m1, a2, m2):
    g, x, y = extended_gcd(m1, m2)
    if (a2 - a1) % g != 0:
        return 0
    lcm = m1 // g * m2
    x0 = (a1 + (a2 - a1) // g * x % (m2 // g) * m1) % lcm
    return x0

def comb_mod(n, k, mod, p):
    if k < 0 or k > n:
        return 0
    result = 1
    e = 0
    for i in range(1, k + 1):
        num = n - k + i
        den = i

        while num % p == 0:
            num = num // p
            e += 1
        while den % p == 0:
            den = den // p
            e -= 1

        result = result * num % mod
        inv = pow(den, -1, mod)
        result = result * inv % mod

    if e >= 0:
        result = result * pow(p, e, mod) % mod
    else:
        return 0
    return result

# Read input
N = int(input())
M = int(input())

total = N // 1000
r = total % M

if r == 0:
    print(1)
else:
    mod1 = 512
    mod2 = 1953125
    p1 = 2
    p2 = 5

    c1 = comb_mod(M, r, mod1, p1)
    c2 = comb_mod(M, r, mod2, p2)

    res = crt(c1, mod1, c2, mod2)
    print(res % 10**9)
0