結果

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

ソースコード

diff #
raw source code 

# 解説を見た。
# 一瞬、不可能では？　と思ったけど、ちゃんと考えて解ける問題だった。

# k>=3のi**(1/k)で区切ろうというのは思いつく。
# 式変形が大変。
# ただ、k*2<=i<=(k+1)*(k+1)のときint(i**0.5)がkになるということに気付けば、
# 式変形が可能そうだとは思うことは可能そう。

import sys
input = sys.stdin.readline

# 高速ベキ乗
def fast_pow(x,y):
    ANS=1
    while y>0:
        if y%2==1:
            ANS=ANS*x
            y-=1

        if y>0:
            x=x*x
            y//=2
    return ANS

mod=998244353

N=int(input())

X=[]

INV20=pow(20,mod-2,mod)
INV2=pow(2,mod-2,mod)

def f(n):
    m=int(n**(1/2))+1

    while n<m*m:
        m-=1

    return (m-1)*m%mod*(m+1)%mod*(8*m*m-5*m-2)%mod*INV20%mod + m*(n-m*m)%mod*(n+m*m-1)%mod*INV2%mod

X=[]
D=dict()

for i in range(3,61):
    for j in range(1,10**6+100):
        k=j**i

        if k<=10**18+10**14:
            X.append(k)
            if k in D:
                D[k].append(i)
            else:
                D[k]=[i]
        else:
            break

X=sorted(set(X))

ANS=0

IC=[0]*61

for i in range(len(X)):
    c=X[i]
    c2=X[i+1]

    for ind in D[c]:
        IC[ind]+=1

    k=1

    for j in range(3,61):
        k=k*IC[j]%mod

        if IC[j]==1:
            break
        

    if c2>N:
        ANS+=(f(N+1)-f(c))*k
        break
    else:
        ANS+=(f(c2)-f(c))*k

    #print(c,c2,ANS)
    ANS%=mod

print(ANS%mod)
0