結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー YuukunA
提出日時 2026-04-19 00:49:12
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 2,147 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 489 ms
コンパイル使用メモリ 20,824 KB
実行使用メモリ 66,408 KB
最終ジャッジ日時 2026-04-19 00:49:42
合計ジャッジ時間 5,932 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 4 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from math import isqrt
import sys

MOD = 998244353
INV2 = 499122177
INV6 = 166374059
INV30 = 432572553


def cube_root_floor(n: int) -> int:
    x = int(n ** (1 / 3))
    while (x + 1) ** 3 <= n:
        x += 1
    while x ** 3 > n:
        x -= 1
    return x


def sum2(n: int) -> int:
    if n <= 0:
        return 0
    a = n % MOD
    b = (n + 1) % MOD
    c = (2 * a + 1) % MOD
    return a * b % MOD * c % MOD * INV6 % MOD


def sum3(n: int) -> int:
    if n <= 0:
        return 0
    a = n % MOD
    b = (n + 1) % MOD
    s = a * b % MOD * INV2 % MOD
    return s * s % MOD


def sum4(n: int) -> int:
    if n <= 0:
        return 0
    a = n % MOD
    b = (n + 1) % MOD
    c = (2 * a + 1) % MOD
    d = (3 * a * a + 3 * a - 1) % MOD
    return a * b % MOD * c % MOD * d % MOD * INV30 % MOD


def range_sum(l: int, r: int) -> int:
    return ((r - l + 1) % MOD) * ((l + r) % MOD) % MOD * INV2 % MOD


def pref(x: int) -> int:
    if x <= 0:
        return 0
    r = isqrt(x)
    m = r - 1
    return (
        2 * sum4(m)
        + 3 * sum3(m)
        + sum2(m)
        + (r % MOD) * range_sum(r * r, x)
    ) % MOD


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

    max_root = cube_root_floor(n)
    inv = [0] * (max_root + 1)
    if max_root >= 1:
        inv[1] = 1
    for i in range(2, max_root + 1):
        inv[i] = (MOD - (MOD // i) * inv[MOD % i]) % MOD

    events = []
    for k in range(3, 61):
        x = 1 << k
        if x > n:
            break
        r = 2
        while x <= n:
            events.append((x, r))
            r += 1
            x = pow(r, k)

    events.sort()

    ans = 0
    prod = 1
    left = 1
    i = 0

    while left <= n:
        next_pos = events[i][0] if i < len(events) else n + 1
        right = min(n, next_pos - 1)

        if left <= right:
            ans = (ans + prod * (pref(right) - pref(left - 1))) % MOD
            left = right + 1
            continue

        while i < len(events) and events[i][0] == left:
            _, r = events[i]
            prod = prod * r % MOD * inv[r - 1] % MOD
            i += 1

    print(ans)


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