結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー Shiny
提出日時 2026-04-18 02:03:41
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,161 ms / 2,000 ms
コード長 1,644 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 284 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 288,128 KB
最終ジャッジ日時 2026-04-18 02:03:51
合計ジャッジ時間 6,834 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import isqrt

MOD = 998244353


def prefix_sqrt_weighted(n: int) -> int:
    if n <= 0:
        return 0

    s = isqrt(n)
    m = s - 1

    whole = (24 * m * m * m * m * m + 105 * m * m * m * m + 150 * m * m * m + 75 * m * m + 6 * m) // 60
    left = s * s
    tail = s * (left + n) * (n - left + 1) // 2
    return (whole + tail) % MOD


def kth_root_floor(n: int, k: int) -> int:
    x = int(round(n ** (1.0 / k)))
    while pow(x + 1, k) <= n:
        x += 1
    while pow(x, k) > n:
        x -= 1
    return x


def main() -> None:
    n = int(sys.stdin.readline())

    if n < 8:
        print(prefix_sqrt_weighted(n))
        return

    cube_lim = kth_root_floor(n, 3)
    inv = [0] * (cube_lim + 1)
    inv[1] = 1
    for x in range(2, cube_lim + 1):
        inv[x] = MOD - (MOD // x) * inv[MOD % x] % MOD

    updates = {}
    k = 3
    while (1 << k) <= n:
        lim = kth_root_floor(n, k)
        for x in range(2, lim + 1):
            value = pow(x, k)
            updates[value] = updates.get(value, 1) * x % MOD * inv[x - 1] % MOD
        k += 1

    answer = 0
    higher_part = 1
    current_left = 1
    last_prefix = 0

    for point in sorted(updates):
        if current_left < point:
            now_prefix = prefix_sqrt_weighted(point - 1)
            answer = (answer + higher_part * (now_prefix - last_prefix)) % MOD
            last_prefix = now_prefix
            current_left = point
        higher_part = higher_part * updates[point] % MOD

    answer = (answer + higher_part * (prefix_sqrt_weighted(n) - last_prefix)) % MOD
    print(answer % MOD)


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