結果

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

ソースコード

diff # 

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    primes = [i for i, val in enumerate(is_prime) if val]
    return primes

def count_exponent(n, p):
    res = 0
    while n > 0:
        n = n // p
        res += n
    return res

N = int(input())
M = int(input())
mod = 10**9

total_1000 = N // 1000
s = total_1000 % M

if s == 0:
    print(1 % mod)
else:
    primes = sieve(M)
    e2 = 0
    e5 = 0
    res = 1
    for p in primes:
        cnt_m = count_exponent(M, p)
        cnt_s = count_exponent(s, p)
        cnt_ms = count_exponent(M - s, p)
        e = cnt_m - cnt_s - cnt_ms
        if e < 0:
            print(0)
            exit()
        if p == 2:
            e2 = e
        elif p == 5:
            e5 = e
        else:
            res = res * pow(p, e, mod) % mod
    if e2 >= 9 or e5 >= 9:
        print(0)
    else:
        res = res * pow(2, e2, mod) % mod
        res = res * pow(5, e5, mod) % mod
        print(res % mod)
0