結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー D M
提出日時 2026-11-17 17:08:28
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 124 ms / 2,000 ms
+ 65µs
コード長 2,812 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,411 ms
コンパイル使用メモリ 349,180 KB
実行使用メモリ 27,436 KB
最終ジャッジ日時 2026-11-17 17:08:33
合計ジャッジ時間 4,959 ms
ジャッジサーバーID
(参考情報)
judge4_0 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

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

using ll = long long;
using i128 = __int128_t;

constexpr ll MOD = 998244353;
constexpr ll INV2 = 499122177;
constexpr ll INV6 = 166374059;
constexpr ll INV30 = 432572553;

ll mul(ll a, ll b) {
    return a * b % MOD;
}

// F(x) = Σ(i * floor(sqrt(i)))  (1 <= i <= x)
ll prefix(ll x) {
    if (x <= 0) return 0;

    // m = floor(sqrt(x))
    ll m = sqrtl((long double)x);

    // 浮動小数点誤差の補正
    while ((i128)(m + 1) * (m + 1) <= x) ++m;
    while ((i128)m * m > x) --m;

    ll n = m - 1;
    ll a = n % MOD;
    ll b = (n + 1) % MOD;
    ll c = (2 * n + 1) % MOD;

    // S2 = Σj^2
    ll s2 = mul(mul(mul(a, b), c), INV6);

    // S3 = Σj^3
    ll t = mul(mul(a, b), INV2);
    ll s3 = mul(t, t);

    // S4 = Σj^4
    ll d = (3 * mul(a, a) % MOD
          + 3 * a % MOD + MOD - 1) % MOD;
    ll s4 = mul(mul(mul(mul(a, b), c), d), INV30);

    // 完全に含まれる区間
    ll full = (2 * s4 + 3 * s3 + s2) % MOD;

    // 最後の区間 [m^2, x]
    ll m2 = m * m;
    ll tail = mul(
        mul(m % MOD, (m2 + x) % MOD),
        (x - m2 + 1) % MOD
    );
    tail = mul(tail, INV2);

    return (full + tail) % MOD;
}

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

    ll N;
    cin >> N;

    // k >= 3 の完全累乗数をイベントとして列挙
    // (a^k, a) を保存
    vector<pair<ll, int>> events;
    int max_a = 2;

    for (int k = 3; k <= 59; ++k) {
        for (ll a = 2;; ++a) {
            i128 p = 1;

            for (int j = 0; j < k && p <= N; ++j) {
                p *= a;
            }

            if (p > N) break;

            events.emplace_back((ll)p, (int)a);
            max_a = max(max_a, (int)a);
        }
    }

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

    // 逆元を前計算
    vector<ll> inv(max_a + 1);
    inv[1] = 1;

    for (int i = 2; i <= max_a; ++i) {
        inv[i] = MOD - mul(MOD / i, inv[MOD % i]);
    }

    ll ans = 0;
    ll weight = 1;
    ll prev_sum = 0;

    for (size_t j = 0; j < events.size();) {
        ll pos = events[j].first;

        // 次のイベント直前までの区間和
        ll next_sum = prefix(pos - 1);
        ll interval = (next_sum - prev_sum + MOD) % MOD;

        ans = (ans + mul(weight, interval)) % MOD;
        prev_sum = next_sum;

        // 同じ位置で発生するイベントをすべて処理
        while (j < events.size() && events[j].first == pos) {
            ll a = events[j].second;

            // (a-1) -> a に変化
            weight = mul(weight, mul(a, inv[a - 1]));
            ++j;
        }
    }

    // 最後のイベントから N まで
    ll tail = (prefix(N) - prev_sum + MOD) % MOD;
    ans = (ans + mul(weight, tail)) % MOD;

    cout << ans << '\n';

    return 0;
}
0