結果

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

ソースコード

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; // Nghịch đảo modulo của 2

// Hàm tính lũy thừa an toàn với __int128 để tránh tràn số
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;
}

// Hàm tính căn bậc k của n chính xác
ll integer_kth_root(ll n, int k) {
    if (k == 1) return n;
    if (n == 1) return 1;
    ll r = pow(n, 1.0/k);
    r += 2;
    while (safe_pow(r, k) > n) r--;
    return r;
}

int main() {
    ll N;
    if (!(cin >> N)) return 0;

    ll ans = 0;
    ll L = 1;

    while (L <= N) {
        // Tìm giá trị các căn bậc k tại điểm L
        vector<ll> roots(61);
        ll prod_others = 1;
        ll R = N;

        // Tính căn bậc 2 riêng để làm mốc nhảy
        roots[2] = integer_kth_root(L, 2);
        ll next_sq = (int128)(roots[2] + 1) * (roots[2] + 1);
        if (next_sq <= N) R = min(R, next_sq - 1);

        // Tính các căn bậc k từ 3 đến 60
        for (int k = 3; k <= 60; k++) {
            roots[k] = integer_kth_root(L, k);
            prod_others = (int128)prod_others * (roots[k] % MOD) % MOD;
            
            // Tìm điểm thay đổi tiếp theo của căn bậc k
            int128 next_pow = safe_pow(roots[k] + 1, k);
            if (next_pow <= (int128)N) {
                R = min(R, (ll)next_pow - 1);
            }
        }

        // Trong đoạn [L, R], giá trị floor(k-th root of i) cho k >= 2 là cố định
        // Riêng căn bậc 2 là roots[2], tích các căn từ 3->60 là prod_others
        // Biểu thức: f(i) = i * floor(sqrt(i)) * prod_others
        // Tổng f(i) = prod_others * roots[2] * sum(i) từ L đến R
        
        ll count = (R - L + 1) % MOD;
        ll sum_i = (int128)(L % MOD + R % MOD) * count % MOD * INV2 % MOD;
        
        ll current_term = (int128)sum_i * (roots[2] % MOD) % MOD;
        current_term = (int128)current_term * prod_others % MOD;

        ans = (ans + current_term) % MOD;
        L = R + 1;
    }

    cout << (ll)ans << endl;

    return 0;
}
0