結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー n_bitand_n_per_3
提出日時 2026-04-19 20:25:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,795 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 249 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 232,500 KB
最終ジャッジ日時 2026-04-19 20:25:29
合計ジャッジ時間 5,174 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
import math
import heapq

MOD = 998244353

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

def sum_n_sqrtn(n):
    if n <= 0:
        return 0
    
    s = math.isqrt(n)
    
    term1_num = (s-1)*s*(s+1)*(8*s*s-5*s-2)
    term1 = (term1_num % MOD) * INV20 % MOD
    
    term2_num = s*(n-s*s+1)*(n+s*s)
    term2 = (term2_num % MOD) * INV2 % MOD
    
    return (term1 + term2) % MOD

def marge_array(X, Y):
    res = []
    i = 0
    j = 0
    while i < len(X) and j < len(Y):
        if X[i] <= Y[j]:
            res.append(X[i])
            i += 1
        else:
            res.append(Y[j])
            j += 1
    while i < len(X):
        res.append(X[i])
        i += 1
    while j < len(Y):
        res.append(Y[j])
        j += 1
    return res

def main():
    N = int(input())

    event = []

    bound = 1
    for p in range(60, 2, -1):
        i = 2
        tmp = []
        while True:
            val = i ** p
            if val > N:
                break
            tmp.append((val, p))
            i += 1
        bound = max(bound, i)
        event = marge_array(event, tmp)

    event.append((N + 1, -1))

    inv = [1]*(bound+1)
    for i in range(2, bound+1):
        q,r = divmod(MOD, i)
        inv[i] = (-(q * inv[r])) % MOD

    prod = 1
    conf = [1] * 61
    ans = 0
    s = 1


    preS = 0
    for curr_val, p in event:
        if s < curr_val:
            S = sum_n_sqrtn(curr_val - 1)
            term = S - preS
            ans = (ans + prod * term) % MOD
            s = curr_val
            S = preS
        
        if p != -1:
            inv_conf = inv[conf[p]]
            prod = prod * inv_conf % MOD
            
            conf[p] += 1
            prod = prod * conf[p] % MOD

    print(ans)

if __name__ == '__main__':
    main()
0