#1160281 (C++23) No.3505 Sum of Prod of Root

• 問題: No.3505 Sum of Prod of Root
• ユーザー: YuukunA
• 提出日時: 2026-04-19 02:10:31
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 347 ms / 2,000 ms
• コード長: 4,355 bytes
• コンパイル時間: 1,745 ms
• コンパイル使用メモリ: 197,300 KB
• 実行使用メモリ: 27,672 KB
• 最終ジャッジ日時: 2026-04-19 02:10:43
• 合計ジャッジ時間: 7,355 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
sample	AC * 1
other	AC * 13

ソースコード

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <vector>

using namespace std;

using int64 = long long;
using i128 = __int128_t;

static constexpr int64 MOD = 998244353;
static constexpr int64 INV2 = 499122177;
static constexpr int64 INV6 = 166374059;
static constexpr int64 INV30 = 432572553;

struct Event {
    int64 position;
    int new_value;

    bool operator<(const Event& other) const {
        return position < other.position;
    }
};

int64 mod_mul(int64 a, int64 b) {
    return static_cast<int64>((i128)a * b % MOD);
}

int64 limited_pow(int64 base, int exp, int64 limit) {
    i128 value = 1;
    for (int i = 0; i < exp; i++) {
        value *= base;
        if (value > limit) return limit + 1;
    }
    return static_cast<int64>(value);
}

int64 floor_sqrt(int64 x) {
    int64 r = sqrtl(static_cast<long double>(x));
    while ((i128)(r + 1) * (r + 1) <= x) r++;
    while ((i128)r * r > x) r--;
    return r;
}

int64 floor_cuberoot(int64 x) {
    int64 r = cbrtl(static_cast<long double>(x));
    while (limited_pow(r + 1, 3, x) <= x) r++;
    while (limited_pow(r, 3, x) > x) r--;
    return r;
}

int64 sum_of_squares(int64 n) {
    if (n <= 0) return 0;
    int64 a = n % MOD;
    int64 b = (n + 1) % MOD;
    int64 c = (2 * a + 1) % MOD;
    return mod_mul(mod_mul(mod_mul(a, b), c), INV6);
}

int64 sum_of_cubes(int64 n) {
    if (n <= 0) return 0;
    int64 a = n % MOD;
    int64 b = (n + 1) % MOD;
    int64 half_sum = mod_mul(mod_mul(a, b), INV2);
    return mod_mul(half_sum, half_sum);
}

int64 sum_of_fourth_powers(int64 n) {
    if (n <= 0) return 0;
    int64 a = n % MOD;
    int64 b = (n + 1) % MOD;
    int64 c = (2 * a + 1) % MOD;
    int64 d = (3 * mod_mul(a, a) + 3 * a - 1) % MOD;
    if (d < 0) d += MOD;
    return mod_mul(mod_mul(mod_mul(mod_mul(a, b), c), d), INV30);
}

int64 arithmetic_sum(int64 left, int64 right) {
    int64 count = (right - left + 1) % MOD;
    int64 ends = (left % MOD + right % MOD) % MOD;
    return mod_mul(mod_mul(count, ends), INV2);
}

// prefix(x) = sum_{i=1}^x i * floor(sqrt(i))
int64 weighted_sqrt_prefix(int64 x) {
    if (x <= 0) return 0;

    int64 root = floor_sqrt(x);
    int64 last_full_root = root - 1;

    int64 full_blocks = (
        2 * sum_of_fourth_powers(last_full_root) +
        3 * sum_of_cubes(last_full_root) +
        sum_of_squares(last_full_root)
    ) % MOD;

    int64 start = static_cast<int64>((i128)root * root);
    int64 partial_block = mod_mul(root % MOD, arithmetic_sum(start, x));

    return (full_blocks + partial_block) % MOD;
}

vector<Event> build_events(int64 n) {
    vector<Event> events;
    events.reserve(1100000);

    for (int k = 3; k <= 60; k++) {
        for (int64 value = 2;; value++) {
            int64 p = limited_pow(value, k, n);
            if (p > n) break;
            events.push_back({p, static_cast<int>(value)});
        }
    }

    sort(events.begin(), events.end());
    return events;
}

vector<int64> build_inverses(int64 n) {
    int max_value = static_cast<int>(floor_cuberoot(n));
    vector<int64> inv(max_value + 1);
    if (max_value >= 1) inv[1] = 1;
    for (int i = 2; i <= max_value; i++) {
        inv[i] = MOD - mod_mul(MOD / i, inv[MOD % i]);
    }
    return inv;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int64 n;
    if (!(cin >> n)) return 0;

    vector<Event> events = build_events(n);
    vector<int64> inv = build_inverses(n);

    int64 answer = 0;
    int64 root_product = 1;  // product of floor(i^(1/k)) for k >= 3 on the current interval
    int64 left = 1;
    size_t event_index = 0;

    while (left <= n) {
        while (event_index < events.size() && events[event_index].position == left) {
            int next_root = events[event_index].new_value;
            root_product = mod_mul(root_product, next_root);
            root_product = mod_mul(root_product, inv[next_root - 1]);
            event_index++;
        }

        int64 right = (event_index < events.size() ? events[event_index].position - 1 : n);
        int64 block_sum = weighted_sqrt_prefix(right) - weighted_sqrt_prefix(left - 1);
        if (block_sum < 0) block_sum += MOD;

        answer += mod_mul(root_product, block_sum);
        answer %= MOD;

        left = right + 1;
    }

    cout << answer << '\n';
    return 0;
}