結果

問題 No.3364 Push_back Operation
コンテスト
ユーザー 回転
提出日時 2025-11-17 22:55:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 781 ms / 2,000 ms
コード長 869 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 76,356 KB
最終ジャッジ日時 2025-11-17 22:55:41
合計ジャッジ時間 17,380 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353
N = int(input())

"""
# https://oeis.org/A345176
def naive(N):
    from itertools import product
    from math import gcd
    ret = 0
    for L in range(1,N+1):
        for i in product(range(1,N+1),repeat=L):
            ret += gcd(*i)%L == 0
    return ret

for i in range(1,21):
    print(i,naive(i))

ans = 0
for i in range(1,N+1):
    ans += pow(N//i,i,MOD)
    ans %= MOD
print(ans)    
"""

ans = 0
now = 1
while(now <= N):
    v = N//now
    v_end = N//v

    a = pow(v,now,MOD)
    r = v
    length = v_end - now + 1
    if(r != 1):
        try:
            ans += a * (pow(r,length,MOD) - 1) * pow(r - 1,-1,MOD)
        except:
            # 998244354?
            for i in range(now,v_end+1):
                ans += a * pow(r,i,MOD)
                ans %= MOD
    else:
        ans += a * length
    ans %= MOD

    now = v_end + 1
print(ans)
0