結果

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

ソースコード

diff # 

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

def main():
    import sys
    N, M = map(int, sys.stdin.read().split())
    total = M * 1000
    X = N // total
    R = N - X * total
    K = R // 1000

    if K == 0:
        print(1)
        return

    MOD = 10**9

    # Sieve of Eratosthenes to find all primes up to M
    sieve = [True] * (M + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(M**0.5) + 1):
        if sieve[i]:
            sieve[i*i::i] = [False] * len(sieve[i*i::i])
    primes = [i for i, is_p in enumerate(sieve) if is_p]

    result = 1
    for p in primes:
        # Numerator: count_p(M! / (M-K)!)
        cnt_numerator = count_p_factorial(M, p) - count_p_factorial(M - K, p)
        # Denominator: count_p(K!)
        cnt_denominator = count_p_factorial(K, p)
        exponent = cnt_numerator - cnt_denominator
        if exponent > 0:
            result = (result * pow(p, exponent, MOD)) % MOD
    print(result)

if __name__ == "__main__":
    main()
0