結果

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

ソースコード

diff #
raw source code 

from heapq import heappop, heappush
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.0 / 3.0))
    while (x + 1) ** 3 <= n:
        x += 1
    while x ** 3 > n:
        x -= 1
    return x


def sum_of_squares(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 sum_of_cubes(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 sum_of_fourth_powers(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 arithmetic_sum(left: int, right: int) -> int:
    count = (right - left + 1) % MOD
    ends = (left + right) % MOD
    return count * ends % MOD * INV2 % MOD


# sum_{i=1}^x i * floor(sqrt(i))
def weighted_sqrt_prefix(x: int) -> int:
    if x <= 0:
        return 0

    root = isqrt(x)
    done = root - 1

    full_blocks = (
        2 * sum_of_fourth_powers(done)
        + 3 * sum_of_cubes(done)
        + sum_of_squares(done)
    ) % MOD

    partial_block = root % MOD * arithmetic_sum(root * root, x) % MOD
    return (full_blocks + partial_block) % 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

    heap = []
    for k in range(3, 61):
        first = 1 << k
        if first > n:
            break
        heappush(heap, (first, k, 2))

    answer = 0
    high_root_product = 1
    left = 1
    prev_prefix = 0

    while left <= n:
        next_event = heap[0][0] if heap else n + 1
        right = min(next_event - 1, n)

        if left <= right:
            current_prefix = weighted_sqrt_prefix(right)
            block_sum = (current_prefix - prev_prefix) % MOD
            answer = (answer + high_root_product * block_sum) % MOD
            prev_prefix = current_prefix
            left = right + 1
            continue

        while heap and heap[0][0] == left:
            _, k, root = heappop(heap)
            high_root_product = high_root_product * root % MOD * inv[root - 1] % MOD

            root += 1
            nxt = pow(root, k)
            if nxt <= n:
                heappush(heap, (nxt, k, root))

    print(answer)


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