結果

問題 No.1039 Project Euler でやれ
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:42:46
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,050 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,576 KB
実行使用メモリ 53,892 KB
最終ジャッジ日時 2025-06-12 15:42:48
合計ジャッジ時間 1,535 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

# Precomputed number of integer partitions for n from 0 to 20
partitions = [
    1,  # p(0)
    1,  # p(1)
    2,  # p(2)
    3,  # p(3)
    5,  # p(4)
    7,  # p(5)
    11, # p(6)
    15, # p(7)
    22, # p(8)
    30, # p(9)
    42, # p(10)
    56, # p(11)
    77, # p(12)
    101,# p(13)
    135,# p(14)
    176,# p(15)
    231,# p(16)
    297,# p(17)
    385,# p(18)
    490,# p(19)
    627  # p(20)
]

def factorize(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    if n > 1:
        factors[n] = 1
    return factors

def main():
    import sys
    M = int(sys.stdin.readline().strip())
    if M == 1:
        print(1)
        return
    factors = factorize(M)
    product = 1
    for e in factors.values():
        product *= partitions[e]
    res = pow(M, product, MOD)
    print(res)

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