結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー Nattt
提出日時 2026-04-18 01:07:26
言語 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  
実行時間 -
コード長 2,514 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,845 ms
コンパイル使用メモリ 177,000 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2026-04-18 01:07:59
合計ジャッジ時間 13,437 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using namespace std;

const long long MOD = 998244353;
const long long inv2 = 499122177; // Modulo invers dari 2

// Fungsi akar integer 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;
}

// Menghitung jumlah (x * v) untuk x dalam rentang [L, R] mod 998244353
long long sum_arithmetic(long long L, long long R, long long v) {
    if (L > R) return 0;
    
    // (L + R) * (R - L + 1) / 2
    long long count = (R - L + 1) % MOD;
    long long sum_LR = (L + R) % MOD;
    
    long long total_x = (count * sum_LR) % MOD * inv2 % MOD;
    
    return (total_x * (v % MOD)) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N;
    if (!(cin >> N)) return 0;
    
    long long ans = 0;
    
    // Titik potong untuk k >= 3 (di mana akar ke-3 atau lebih tinggi bernilai >= 2)
    // Akar pangkat 3 dari 10^18 adalah 10^6
    long long cbrt_N = cbrt(N) + 2; 
    while (cbrt_N * cbrt_N * cbrt_N > N) cbrt_N--;
    
    // 1. Loop per blok untuk nilai yang akarnya (k >= 3) >= 2
    // Blok ini berjalan cepat karena maksimal x <= 10^6
    for (long long x = 1; x <= min(N, cbrt_N * cbrt_N * cbrt_N); x++) {
        long long W = 1;
        long long root2 = isqrt(x);
        W = (W * (root2 % MOD)) % MOD;
        
        long long v = x;
        int k = 3;
        while (true) {
            long long r = pow((long double)v, 1.0L / k);
            while (pow(r, k) > v) r--;
            while (pow(r + 1, k) <= v) r++;
            
            if (r == 1) break;
            W = (W * (r % MOD)) % MOD;
            k++;
        }
        ans = (ans + (x % MOD) * W) % MOD;
    }
    
    // 2. Untuk x > cbrt_N^3, semua akar pangkat k (k >= 3) pasti bernilai 1!
    // Jadi W hanya ditentukan oleh akar kuadratnya (k = 2)
    long long L = cbrt_N * cbrt_N * cbrt_N + 1;
    if (L <= N) {
        long long start_v = isqrt(L);
        long long end_v = isqrt(N);
        
        for (long long v = start_v; v <= end_v; v++) {
            // Rentang indeks x di mana isqrt(x) == v
            long long cur_L = max(L, v * v);
            long long cur_R = min(N, (v + 1) * (v + 1) - 1);
            
            if (cur_L <= cur_R) {
                ans = (ans + sum_arithmetic(cur_L, cur_R, v)) % MOD;
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}
0