結果

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

ソースコード

diff #
raw source code 

import sys
import math
import heapq

# 定数設定
MOD = 998244353

# モジュラ逆元 (割り算用)
# フェルマーの小定理により a^(MOD-2) = a^(-1) (mod MOD)
INV2 = pow(2, MOD - 2, MOD)
INV20 = pow(20, MOD - 2, MOD)

def sum_n_sqrtn(n):
    """
    sum_{i=1}^n (i * floor(sqrt(i))) mod MOD を計算する関数
    """
    if n <= 0:
        return 0
    
    s = math.isqrt(n)
    
    # Term 1: (s-1)*s*(s+1)*(8s^2 - 5s - 2) / 20
    # Pythonは多倍長整数を扱えるため、分子を計算してからMODをとるのが安全かつ簡単です
    term1_num = (s - 1) * s * (s + 1) * (8 * s * s - 5 * s - 2)
    term1 = (term1_num % MOD) * INV20 % MOD
    
    # Term 2: s * (n - s*s + 1) * (n + s*s) / 2
    # 区間 [s^2, n] の総和 * s
    term2_num = s * (n - s * s + 1) * (n + s * s)
    term2 = (term2_num % MOD) * INV2 % MOD
    
    return (term1 + term2) % MOD


def sum_n_sqrtn(n):
    """
    sum_{i=1}^n (i * floor(sqrt(i))) mod MOD を計算する関数
    """
    if n <= 0:
        return 0
    
    s = math.isqrt(n)
    
    # Term 1: (s-1)*s*(s+1)*(8s^2 - 5s - 2) / 20
    # Pythonは多倍長整数を扱えるため、分子を計算してからMODをとるのが安全かつ簡単です
    term1_num = (s - 1) * s * (s + 1) * (8 * s * s - 5 * s - 2)
    term1 = (term1_num % MOD) * INV20 % MOD
    
    # Term 2: s * (n - s*s + 1) * (n + s*s) / 2
    # 区間 [s^2, n] の総和 * s
    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())

    # 優先度付きキュー (Min-Heap)
    # 要素は (次の位置, 指数p)
    pq = []

    # C++: for (ll p=3; p <= 60; p++)
    bound = 1
    for p in range(60, 2, -1):
        i = 2
        tmp = []
        while True:
            # Pythonは自動的に多倍長整数になるため、オーバーフローチェックは不要
            # ただし N を超えたらループを抜ける
            val = i ** p
            if val > N:
                break
            tmp.append((val, p))
            i += 1
        bound = max(bound, i)
        pq = marge_array(pq, tmp)

    # 番兵
    pq.append((N + 1, -1))

    # 逆元テーブル
    # MOD = x * (MOD//x) + MOD % x  => x^(-1) = -(MOD//x) * (MOD % x)^(-1) mod MOD
    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  # C++: vector<mint> Conf(61, 1)
    ans = 0
    s = 1


    preS = 0
    # スイープライン処理
    for curr_val, p in pq:
        # 現在の位置 s から 次のイベント位置 curr_val までの区間を加算
        if s < curr_val:
            S = sum_n_sqrtn(curr_val - 1)
            term = S - preS
            ans = (ans + prod * term) % MOD
            s = curr_val
            preS = S
        
        # 指数のカウント更新
        if p != -1:
            # prod /= conf[p]
            # prod *= (conf[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