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

• 問題: No.3505 Sum of Prod of Root
• ユーザー: sient
• 提出日時: 2026-04-17 23:37:57
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,074 bytes
• コンパイル時間: 2,525 ms
• コンパイル使用メモリ: 341,440 KB
• 実行使用メモリ: 14,072 KB
• 最終ジャッジ日時: 2026-04-17 23:38:32
• 合計ジャッジ時間: 7,583 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	-- * 1
other	AC * 3 TLE * 1 -- * 9

ソースコード

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

using ull = unsigned long long;
using u128 = __uint128_t;
static const long long MOD = 998244353;

long long mod_mul(long long a, long long b) {
    return (long long)((__int128)a * b % MOD);
}

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e > 0) {
        if (e & 1) r = mod_mul(r, a);
        a = mod_mul(a, a);
        e >>= 1;
    }
    return r;
}

ull power_limit(ull a, int k, ull lim) {
    u128 res = 1;
    for (int i = 0; i < k; ++i) {
        res *= (u128)a;
        if (res > lim) return lim + 1;
    }
    return (ull)res;
}

ull iroot(ull n, int k) {
    long double x = pow((long double)n, 1.0L / k);
    ull r = max<ull>(1, (ull)x);
    while (power_limit(r + 1, k, n) <= n) ++r;
    while (power_limit(r, k, n) > n) --r;
    return r;
}

long long sum_arith_mod(ull x) {
    if (x == 0) return 0;
    u128 a = x, b = x + 1;
    if ((a & 1) == 0) a >>= 1;
    else b >>= 1;
    return (long long)((a * b) % MOD);
}

long long prefix_T(ull M) {
    if (M == 0) return 0;

    ull s = sqrt((long double)M);
    while ((u128)(s + 1) * (s + 1) <= M) ++s;
    while ((u128)s * s > M) --s;

    ull m = s - 1;

    long long n = (long long)(m % MOD);
    long long n1 = (n + 1) % MOD;
    long long two_n1 = (2 * n + 1) % MOD;
    long long three_n2_3n_1 = ( (3LL * n % MOD * n) % MOD + 3LL * n - 1 + MOD ) % MOD;

    const long long INV2 = mod_pow(2, MOD - 2);
    const long long INV6 = mod_pow(6, MOD - 2);
    const long long INV30 = mod_pow(30, MOD - 2);

    long long S1 = mod_mul(mod_mul(n, n1), INV2);
    long long S2 = mod_mul(mod_mul(mod_mul(n, n1), two_n1), INV6);
    long long S3 = mod_mul(S1, S1);
    long long S4 = mod_mul(mod_mul(mod_mul(mod_mul(n, n1), two_n1), three_n2_3n_1), INV30);

    long long full_blocks = (2LL * S4 + 3LL * S3 + S2) % MOD;

    ull sq = s * s;
    long long tail = (sum_arith_mod(M) - sum_arith_mod(sq - 1) + MOD) % MOD;
    long long tail_part = mod_mul((long long)(s % MOD), tail);

    return (full_blocks + tail_part) % MOD;
}

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

    ull N;
    cin >> N;

    vector<ull> bp;
    bp.push_back(1);
    bp.push_back(N + 1);

    for (int k = 3; ; ++k) {
        if (power_limit(2, k, N) > N) break;
        for (ull a = 2; ; ++a) {
            ull v = power_limit(a, k, N);
            if (v > N) break;
            bp.push_back(v);
        }
    }

    sort(bp.begin(), bp.end());
    bp.erase(unique(bp.begin(), bp.end()), bp.end());

    long long ans = 0;

    for (int i = 0; i + 1 < (int)bp.size(); ++i) {
        ull L = bp[i];
        ull R = bp[i + 1] - 1;
        if (L > R) continue;

        long long coeff = 1;
        for (int k = 3; ; ++k) {
            ull r = iroot(L, k);
            if (r <= 1) break;
            coeff = mod_mul(coeff, (long long)(r % MOD));
        }

        long long block = (prefix_T(R) - prefix_T(L - 1) + MOD) % MOD;
        ans = (ans + mod_mul(coeff, block)) % MOD;
    }

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