結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー n_bitand_n_per_3
提出日時 2026-04-19 20:26:59
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,510 ms / 2,000 ms
コード長 2,656 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 299 ms
コンパイル使用メモリ 85,760 KB
実行使用メモリ 150,912 KB
最終ジャッジ日時 2026-04-19 20:27:15
合計ジャッジ時間 7,123 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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_a_b(a, b):
    """
    半開区間 [a, b) の総和を求める
    sum_{i=a}^{b-1} (i * floor(sqrt(i)))
    """
    return (sum_n_sqrtn(b - 1) - sum_n_sqrtn(a - 1) + MOD) % MOD

def main():
    # 入力の受け取り
    try:
        input_str = sys.stdin.read().strip()
        if not input_str:
            return
        N = int(input_str)
    except ValueError:
        return

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

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

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

    prod = 1
    conf = [1] * 61  # C++: vector<mint> Conf(61, 1)
    ans = 0
    s = 1

    # スイープライン処理
    while pq:
        curr_val, p = heapq.heappop(pq)
        
        # 現在の位置 s から 次のイベント位置 curr_val までの区間を加算
        if s < curr_val:
            term = sum_a_b(s, curr_val)
            ans = (ans + prod * term) % MOD
            s = curr_val
        
        # 指数のカウント更新
        if p != -1:
            # prod /= conf[p]
            # prod *= (conf[p] + 1)
            # 割り算は逆元を掛ける
            inv_conf = pow(conf[p], MOD - 2, MOD)
            prod = prod * inv_conf % MOD
            
            conf[p] += 1
            prod = prod * conf[p] % MOD

    print(ans)

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