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

• 問題: No.3505 Sum of Prod of Root
• ユーザー: Naru820
• 提出日時: 2026-03-17 15:15:45
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,741 bytes
• コンパイル時間: 1,504 ms
• コンパイル使用メモリ: 190,980 KB
• 実行使用メモリ: 28,000 KB
• 最終ジャッジ日時: 2026-04-17 19:40:33
• 合計ジャッジ時間: 9,521 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

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

ソースコード

// gemini 3.1proのテスト
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

long long MOD = 998244353;

// 繰り返し二乗法による累乗と逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}
long long modInverse(long long n) { return power(n, MOD - 2); }

long long inv2, inv6, inv4, inv30;
void initInverses() {
    inv2 = modInverse(2);
    inv6 = modInverse(6);
    inv4 = modInverse(4);
    inv30 = modInverse(30);
}

// べき乗和の公式
long long S2(long long x) {
    x %= MOD;
    return x * (x + 1) % MOD * (2 * x + 1) % MOD * inv6 % MOD;
}
long long S3(long long x) {
    x %= MOD;
    long long res = x * (x + 1) % MOD * inv2 % MOD;
    return res * res % MOD;
}
long long S4(long long x) {
    x %= MOD;
    long long res = x * (x + 1) % MOD * (2 * x + 1) % MOD;
    long long term = (3 * x % MOD * x % MOD + 3 * x % MOD - 1 + MOD) % MOD;
    return res * term % MOD * inv30 % MOD;
}

// S(M) = \sum_{i=1}^M i * floor(sqrt(i))
long long S(long long M) {
    if (M <= 0) return 0;
    long long V = sqrt(M);
    while ((V + 1) * (V + 1) <= M) V++;
    while (V * V > M) V--;
    
    long long v1 = V - 1;
    long long part1 = (2 * S4(v1) + 3 * S3(v1) + S2(v1)) % MOD;
    
    long long M_mod = M % MOD;
    long long V2_mod = (V % MOD) * (V % MOD) % MOD;
    long long count = (M_mod - V2_mod + 1 + MOD) % MOD;
    long long sum_i = (V2_mod + M_mod) % MOD * count % MOD * inv2 % MOD;
    
    long long part2 = (V % MOD) * sum_i % MOD;
    
    return (part1 + part2) % MOD;
}

// h(L) = \prod_{k=3}^{60} floor(L^{1/k})
long long calc_h(long long L) {
    long long res = 1;
    for (int k = 3; k <= 60; ++k) {
        long long r = max(1LL, (long long)round(pow(L, 1.0 / k)));
        while (true) {
            __int128 p = 1; bool over = false;
            for (int i = 0; i < k; ++i) { p *= r; if (p > L) { over = true; break; } }
            if (over) { r--; } else {
                __int128 p2 = 1; bool over2 = false; long long rp1 = r + 1;
                for (int i = 0; i < k; ++i) { p2 *= rp1; if (p2 > L) { over2 = true; break; } }
                if (!over2) r++; else break;
            }
        }
        r %= MOD;
        if (r == 1) break; // r=1なら以降のkもすべて1なので打ち切る
        res = res * r % MOD;
    }
    return res;
}

int main() {
    initInverses();
    long long N;
    if (!(cin >> N)) return 0;
    
    // 変化点 (a^k) を列挙
    vector<long long> bounds;
    for (long long a = 2; a <= 1000000; ++a) {
        long long p = a * a * a;
        if (p > N) break;
        while (true) {
            bounds.push_back(p);
            if (N / a < p) break;
            p *= a;
        }
    }
    bounds.push_back(1);
    bounds.push_back(N + 1);
    
    // ソート＆重複削除
    vector<long long> valid_bounds;
    for(long long b : bounds) {
        if (b <= N + 1) valid_bounds.push_back(b);
    }
    sort(valid_bounds.begin(), valid_bounds.end());
    valid_bounds.erase(unique(valid_bounds.begin(), valid_bounds.end()), valid_bounds.end());
    
    // 区間ごとに和を計算
    long long ans = 0;
    for (size_t i = 0; i < valid_bounds.size() - 1; ++i) {
        long long L = valid_bounds[i];
        long long R = valid_bounds[i+1] - 1;
        if (L > R) continue;
        
        long long h_val = calc_h(L);
        long long sum_interval = (S(R) - S(L - 1) + MOD) % MOD;
        
        ans = (ans + h_val * sum_interval) % MOD;
    }
    
    cout << ans << "\n";
    return 0;
}