結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー Nattt
提出日時 2026-04-18 01:19:45
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 3,443 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,077 ms
コンパイル使用メモリ 190,992 KB
実行使用メモリ 14,072 KB
最終ジャッジ日時 2026-04-18 01:20:20
合計ジャッジ時間 6,214 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 3 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const long long MOD = 998244353;
long long inv30, inv6, inv2;

// Fungsi untuk menghitung pangkat modulo
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;
}

// Fungsi Modular Inverse yang PASTI akurat
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// Pangkat aman anti overflow
long long my_pow(long long x, int k) {
    long long res = 1;
    for (int i = 0; i < k; i++) {
        if (__builtin_mul_overflow(res, x, &res)) return 2e18; 
    }
    return res;
}

// Akar kuadrat presisi tinggi
long long isqrt(long long n) {
    if (n == 0) return 0;
    long long r = sqrt(n);
    while (r * r > n) r--;
    while ((r + 1) * (r + 1) <= n) r++;
    return r;
}

// Akar pangkat k presisi tinggi
long long iroot(long long n, int k) {
    if (k == 1) return n;
    if (k == 2) return isqrt(n);
    long long ans = pow((long double)n, 1.0L / k);
    while (my_pow(ans, k) > n) ans--;
    while (my_pow(ans + 1, k) <= n) ans++;
    return ans;
}

// Rumus Sakti O(1) untuk menghitung Deret i * floor(sqrt(i))
long long S(long long n) {
    if (n == 0) return 0;
    long long R = isqrt(n);
    long long k = (R - 1) % MOD;
    
    long long S2 = k * (k + 1) % MOD * (2 * k + 1) % MOD * inv6 % MOD;
    long long S3 = k * (k + 1) % MOD * inv2 % MOD;
    S3 = S3 * S3 % MOD;
    
    long long S4 = k * (k + 1) % MOD * (2 * k + 1) % MOD;
    long long S4_part2 = (3 * k % MOD * k % MOD + 3 * k % MOD - 1 + MOD) % MOD;
    S4 = S4 * S4_part2 % MOD * inv30 % MOD;
    
    long long res = (2 * S4 + 3 * S3 + S2) % MOD;
    
    long long n_mod = n % MOD;
    long long R2_mod = (R % MOD) * (R % MOD) % MOD;
    
    long long terms = (n_mod - R2_mod + 1 + MOD) % MOD;
    long long sum_ends = (n_mod + R2_mod) % MOD;
    long long part2 = terms * sum_ends % MOD * inv2 % MOD;
    part2 = part2 * (R % MOD) % MOD;
    
    res = (res + part2) % MOD;
    return res;
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // Hitung invers dengan aman
    inv30 = modInverse(30);
    inv6 = modInverse(6);
    inv2 = modInverse(2);
    
    long long N;
    if (!(cin >> N)) return 0;
    
    vector<long long> pts;
    pts.push_back(1);
    pts.push_back(N + 1);
    
    // Kumpulkan titik di mana akar >= 3 berubah (hanya ~1 juta operasi, instan)
    for (int k = 3; k <= 60; k++) {
        long long x = 2;
        while (true) {
            long long p = my_pow(x, k);
            if (p > N) break;
            pts.push_back(p);
            x++;
        }
    }
    
    sort(pts.begin(), pts.end());
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
    
    long long ans = 0;
    
    // Proses per interval 
    for (size_t i = 0; i < pts.size() - 1; i++) {
        long long L = pts[i];
        long long R = pts[i+1] - 1;
        
        long long W = 1;
        for (int k = 3; k <= 60; k++) {
            long long root = iroot(L, k);
            if (root == 1) break; 
            W = W * (root % MOD) % MOD;
        }
        
        long long sum_S = (S(R) - S(L - 1) + MOD) % MOD;
        ans = (ans + W * sum_S) % MOD;
    }
    
    cout << ans << "\n";
    return 0;
}
0