結果

問題 No.2902 ZERO!!
コンテスト
ユーザー NP
提出日時 2024-09-27 22:36:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 226 ms / 2,000 ms
コード長 834 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 100,224 KB
最終ジャッジ日時 2024-09-27 22:36:18
合計ジャッジ時間 5,759 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

MOD = 998244353
N = int(input())
e_p = {}
is_prime = [True] * (N + 1)
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 in range(2, N + 1) if is_prime[i]]
max_e = 0
e_p_list = []
for p in primes:
    e = 0
    n = N
    while n:
        n //= p
        e += n
    e_p_list.append(e)
    max_e = max(max_e, e)
E = max_e
T = [1] * (E + 2)
for e in e_p_list:
    c = e
    k = 1
    while c > 0:
        k_l = e // (c + 1) + 1
        k_r = e // c if c > 0 else e
        if k_l > k_r:
            c -= 1
            continue
        for k in range(k_l, k_r + 1):
            T[k] = T[k] * (c + 1) % MOD
        c -= 1
a = 0
for k in range(1, E + 1):
    diff = (T[k] - T[k + 1]) % MOD
    a = (a + k * diff) % MOD
print(a)
0