結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー lif4635
提出日時 2026-04-18 18:56:06
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,489 ms / 2,000 ms
コード長 1,131 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 110 ms
コンパイル使用メモリ 85,624 KB
実行使用メモリ 156,300 KB
最終ジャッジ日時 2026-04-18 18:56:14
合計ジャッジ時間 6,524 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

"""
くね。

k = 1, 2 さえ処理すれば ok
k = 1 : 自明
k = 2 : s = isqrt(n) - 1
"""

from math import isqrt
from collections import deque
import sys

mod = 998244353
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : (int(_) for _ in input().split())
LI = lambda : list(int(_) for _ in input().split())
SI = lambda : input()

n = II()

def calc(n):
    v = isqrt(n) - 1
    s2 = v*(v+1)*(2*v+1)//6 % mod
    s3 = (v*(v+1)//2)**2 % mod
    s4 = v*(v+1)*(2*v+1)*(3*v*v+3*v-1)//30 % mod
    tmp = 2*s4 + 3*s3 + s2

    v += 1
    return (tmp + v*(v*v+n)*(n-v*v+1)//2) % mod

lim = int(n ** (1 / 3) + 10)
inv = [0] + [pow(i, -1, mod) for i in range(1, lim)]

eve = []
for x in range(2, lim):
    p = x ** 3
    m = x * inv[x-1] % mod
    while p <= n:
        eve.append((p, m))
        p *= x

eve.sort()
eve.append((n+1, -1))
ans = 0
i = 0
cc = 1
pv = 0
while i < len(eve):
    p = eve[i][0]
    nv = calc(p - 1)
    ans += (nv - pv) * cc % mod
    pv = nv
    if i == len(eve) - 1: break
    
    while i < len(eve) and eve[i][0] == p:
        cc = (cc * eve[i][1]) % mod
        i += 1

print(ans % mod)
0