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

• 問題: No.3505 Sum of Prod of Root
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 05:44:58
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,539 ms / 2,000 ms
• コード長: 3,167 bytes
• コンパイル時間: 2,512 ms
• コンパイル使用メモリ: 342,084 KB
• 実行使用メモリ: 27,472 KB
• 最終ジャッジ日時: 2026-04-18 05:45:06
• 合計ジャッジ時間: 7,433 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

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

ソースコード

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

using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;

static const ll MOD = 998244353;

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

ll addm(ll a, ll b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

ll subm(ll a, ll b) {
    a -= b;
    if (a < 0) a += MOD;
    return a;
}

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

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

ll take_mod(ull x) {
    return (ll)(x % MOD);
}

ll sum1(ull n) {
    ll a = take_mod(n), b = take_mod(n + 1);
    return mulm(mulm(a, b), (MOD + 1) / 2);
}

ll sum2(ull n) {
    ll a = take_mod(n), b = take_mod(n + 1), c = take_mod(2 * n + 1);
    return mulm(mulm(mulm(a, b), c), modpow(6, MOD - 2));
}

ll sum3(ull n) {
    ll s = sum1(n);
    return mulm(s, s);
}

ll sum4(ull n) {
    ll a = take_mod(n), b = take_mod(n + 1), c = take_mod(2 * n + 1);
    ll d = subm(addm(mulm(3, mulm(a, a)), mulm(3, a)), 1);
    return mulm(mulm(mulm(mulm(a, b), c), d), modpow(30, MOD - 2));
}

ll sum_range(ull l, ull r) {
    if (l > r) return 0;
    ll a = take_mod(l + r);
    ll b = take_mod(r - l + 1);
    return mulm(mulm(a, b), (MOD + 1) / 2);
}

ll pref(ull m) {
    if (m == 0) return 0;

    ull rt = isqrt2(m);
    ull t = rt - 1;

    ll full = addm(addm(mulm(2, sum4(t)), mulm(3, sum3(t))), sum2(t));

    ull l = rt * rt;
    ll last = mulm(take_mod(rt), sum_range(l, m));

    return addm(full, last);
}

struct Event {
    ull val;
    int a;
    bool operator<(const Event& other) const {
        return val < other.val;
    }
};

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

    ull n;
    cin >> n;

    vector<Event> ev;
    int maxa = 1;

    for (int k = 3; k <= 60; k++) {
        for (ull a = 2;; a++) {
            i128 v = 1;
            for (int t = 0; t < k; t++) {
                v *= a;
                if (v > (i128)n) break;
            }
            if (v > (i128)n) break;
            ev.push_back({(ull)v, (int)a});
            if ((int)a > maxa) maxa = (int)a;
        }
    }

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

    vector<ll> inv(maxa + 1, 1);
    for (int i = 2; i <= maxa; i++) {
        inv[i] = MOD - mulm(MOD / i, inv[MOD % i]);
    }

    ll ans = 0;
    ll curProd = 1;
    ull cur = 1;

    int i = 0, m = (int)ev.size();

    while (i < m) {
        ull v = ev[i].val;

        if (cur <= v - 1) {
            ll block = subm(pref(v - 1), pref(cur - 1));
            ans = addm(ans, mulm(curProd, block));
        }

        while (i < m && ev[i].val == v) {
            int a = ev[i].a;
            curProd = mulm(curProd, a);
            curProd = mulm(curProd, inv[a - 1]);
            i++;
        }

        cur = v;
    }

    if (cur <= n) {
        ll block = subm(pref(n), pref(cur - 1));
        ans = addm(ans, mulm(curProd, block));
    }

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