結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー M Mahrus Qusaeri
提出日時 2026-04-18 01:10:51
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 1,061 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 640 ms
コンパイル使用メモリ 20,828 KB
実行使用メモリ 511,632 KB
最終ジャッジ日時 2026-04-18 01:11:22
合計ジャッジ時間 9,108 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 1 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import isqrt
input = sys.stdin.readline
MOD = 998244353
def modinv(a, m=MOD): return pow(a, m-2, m)
def solve():
    N = int(input())
    bp_changes = {}
    k = 2
    while True:
        m_max = int(N**(1.0/k)) + 2
        found = False
        for m in range(2, m_max+1):
            val = m**k
            if val > N: break
            if val not in bp_changes: bp_changes[val] = []
            bp_changes[val].append((m, k))
            found = True
        if not found or k > 63: break
        k += 1
    bps = sorted(set(list(bp_changes.keys()) + [1, N+1]))
    C_mod = 1
    ans = 0
    inv2 = modinv(2)
    prev = 1
    for bp in bps:
        if bp > prev:
            s, e = prev, min(bp-1, N)
            if s <= e:
                cnt = e-s+1
                sum_i = (s+e)%MOD * (cnt%MOD) % MOD * inv2 % MOD
                ans = (ans + C_mod * sum_i) % MOD
        if bp in bp_changes:
            for m, k in bp_changes[bp]:
                C_mod = C_mod * m % MOD * modinv(m-1) % MOD
        prev = bp
    print(ans)
solve()
0