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

• 問題: No.3505 Sum of Prod of Root
• ユーザー: e032_Ashmit_Rana
• 提出日時: 2026-04-19 20:12:48
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 234 ms / 2,000 ms
• コード長: 3,551 bytes
• コンパイル時間: 3,987 ms
• コンパイル使用メモリ: 343,236 KB
• 実行使用メモリ: 27,380 KB
• 最終ジャッジ日時: 2026-04-19 20:13:00
• 合計ジャッジ時間: 3,926 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using i128 = __int128_t;

static constexpr int64 MOD = 998244353;
static constexpr int MAX_K = 60;

struct Event {
    int64 x;
    int k;
    int root;
    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return k < other.k;
    }
};

int64 mod_pow(int64 a, int64 e) {
    int64 r = 1;
    while (e > 0) {
        if (e & 1) r = (i128)r * a % MOD;
        a = (i128)a * a % MOD;
        e >>= 1;
    }
    return r;
}

int64 sum_upto(int64 n) {
    if (n <= 0) return 0;
    static const int64 inv2 = mod_pow(2, MOD - 2);
    return (i128)(n % MOD) * ((n + 1) % MOD) % MOD * inv2 % MOD;
}

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

int64 prefix_i_sqrt(int64 n) {
    if (n <= 0) return 0;

    static const int64 inv2 = mod_pow(2, MOD - 2);
    static const int64 inv6 = mod_pow(6, MOD - 2);
    static const int64 inv30 = mod_pow(30, MOD - 2);

    int64 m = isqrt_int(n);
    int64 t = m - 1;

    int64 tm = t % MOD;
    int64 tp1 = (t + 1) % MOD;
    int64 two_t_plus_1 = (2 * tm + 1) % MOD;

    int64 s2 = (i128)tm * tp1 % MOD * two_t_plus_1 % MOD * inv6 % MOD;

    int64 tri = (i128)tm * tp1 % MOD * inv2 % MOD;
    int64 s3 = (i128)tri * tri % MOD;

    int64 quad_poly = ((i128)3 * tm % MOD * tm + (i128)3 * tm - 1) % MOD;
    if (quad_poly < 0) quad_poly += MOD;
    int64 s4 = (i128)tm * tp1 % MOD * two_t_plus_1 % MOD * quad_poly % MOD * inv30 % MOD;

    int64 full_blocks = ((i128)2 * s4 + (i128)3 * s3 + s2) % MOD;

    int64 block_start = m * m;
    int64 partial_sum = (sum_upto(n) - sum_upto(block_start - 1) + MOD) % MOD;
    int64 partial = (i128)(m % MOD) * partial_sum % MOD;

    return (full_blocks + partial) % MOD;
}

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

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

    int64 N;
    cin >> N;

    vector<Event> events;
    int max_root = 1;
    for (int k = 3; k <= MAX_K; ++k) {
        for (int64 a = 2;; ++a) {
            int64 x = pow_limited(a, k, N);
            if (x > N) break;
            events.push_back({x, k, (int)a});
            max_root = max<int64>(max_root, a);
        }
    }
    sort(events.begin(), events.end());

    vector<int64> inv(max_root + 1);
    inv[1] = 1;
    for (int i = 2; i <= max_root; ++i) {
        inv[i] = MOD - (i128)(MOD / i) * inv[MOD % i] % MOD;
    }

    array<int, MAX_K + 1> roots{};
    roots.fill(1);

    int64 high_prod = 1;
    int64 ans = 0;
    int64 left = 1;

    for (size_t i = 0; i < events.size();) {
        int64 x = events[i].x;
        if (left < x) {
            int64 segment = (prefix_i_sqrt(x - 1) - prefix_i_sqrt(left - 1) + MOD) % MOD;
            ans = (ans + (i128)high_prod * segment) % MOD;
        }

        while (i < events.size() && events[i].x == x) {
            int k = events[i].k;
            int nr = events[i].root;
            high_prod = (i128)high_prod * inv[roots[k]] % MOD * nr % MOD;
            roots[k] = nr;
            ++i;
        }
        left = x;
    }

    if (left <= N) {
        int64 segment = (prefix_i_sqrt(N) - prefix_i_sqrt(left - 1) + MOD) % MOD;
        ans = (ans + (i128)high_prod * segment) % MOD;
    }

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