結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

typedef long long ll;
typedef __int128_t int128;

const ll MOD = 998244353;
const ll INV2 = 499122177;
const ll INV6 = 166374059;

// Hàm tính tổng i * floor(sqrt(i)) từ L đến R
ll sum_i_sqrt_i(ll L, ll R) {
    ll total = 0;
    ll s = sqrt(L);
    if ((int128)(s + 1) * (s + 1) <= L) s++;
    if ((int128)s * s > L) s--;

    while (L <= R) {
        ll next_boundary = (int128)(s + 1) * (s + 1);
        ll current_R = min((int128)R, (int128)next_boundary - 1);
        
        // Tổng i trong đoạn [L, current_R]
        ll n = (current_R - L + 1) % MOD;
        ll sum_i = (int128)(L % MOD + current_R % MOD) * n % MOD * INV2 % MOD;
        
        // Cộng vào tổng: sum(i) * s
        total = (total + (int128)sum_i * (s % MOD)) % MOD;
        
        L = current_R + 1;
        s++;
    }
    return total;
}

int128 safe_pow(ll base, int exp) {
    int128 res = 1;
    for (int i = 0; i < exp; i++) {
        res *= (int128)base;
        if (res > (int128)2e18) return (int128)2e18 + 7;
    }
    return res;
}

ll get_kth_root(ll n, int k) {
    if (k == 1) return n;
    ll r = pow(n, 1.0/k);
    r += 2;
    while (safe_pow(r, k) > n) r--;
    return r;
}

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

    ll N;
    if (!(cin >> N)) return 0;

    // Danh sách các điểm mà floor(root_k(i)) thay đổi cho k >= 3
    vector<ll> checkpoints;
    checkpoints.push_back(1);
    checkpoints.push_back(N + 1);
    for (int k = 3; k <= 60; k++) {
        for (ll r = 1; ; r++) {
            int128 p = safe_pow(r, k);
            if (p > N) break;
            checkpoints.push_back((ll)p);
        }
    }
    sort(checkpoints.begin(), checkpoints.end());
    checkpoints.erase(unique(checkpoints.begin(), checkpoints.end()), checkpoints.end());

    ll total_ans = 0;
    for (size_t i = 0; i < checkpoints.size() - 1; i++) {
        ll L = checkpoints[i];
        ll R = checkpoints[i+1] - 1;
        if (L > N) break;

        // Tại mọi i trong [L, R], các căn bậc k >= 3 là cố định
        ll prod_others = 1;
        for (int k = 3; k <= 60; k++) {
            ll r_k = get_kth_root(L, k);
            prod_others = (int128)prod_others * (r_k % MOD) % MOD;
        }

        // Tính sum(i * floor(sqrt(i))) trong đoạn [L, R]
        ll s_val = sum_i_sqrt_i(L, R);
        total_ans = (total_ans + (int128)s_val * prod_others) % MOD;
    }

    cout << total_ans << endl;
    return 0;
}
0