結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー よいちなすの
提出日時 2026-04-18 00:55:19
言語 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,037 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,361 ms
コンパイル使用メモリ 342,196 KB
実行使用メモリ 25,340 KB
最終ジャッジ日時 2026-04-18 00:56:03
合計ジャッジ時間 9,858 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 1 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

typedef __int128_t int128;
const long long MOD = 998244353;

long long sum(long long l, long long r) {
    if (l > r) return 0;
    int128 first = l;
    int128 last = r;
    int128 num = (r - l + 1);
    int128 res = (first + last) * num / 2;
    return (long long)(res % MOD);
}

int main() {
    long long N;
    cin >> N;

    map<long long, long long> mp;
    mp[1] = 1;

    for (int k = 3; k <= 60; ++k) {
        for (long long v = 2; ; ++v) {
            int128 val = 1;
            bool ok = false;
            for (int p = 0; p < k; ++p) {
                if (__builtin_mul_overflow(val, v, &val)) { ok = true; break; }
            }
            if (ok || val > N) break;
            mp[(long long)val] = 1; 
        }
    }

    for (long long v = 1; v * v <= N; ++v) {
        mp[v * v] = 1;
    }

    vector<long long> pos;
    for (auto const& [p, _] : mp) pos.push_back(p);
    pos.push_back(N + 1);

    long long tot = 0;

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

        long long X = 1;
        
        long long s2 = sqrt(L);
        while ((s2 + 1) * (s2 + 1) <= L) s2++;
        while (s2 * s2 > L) s2--;
        X = (X * (s2 % MOD)) % MOD;

        for (int k = 3; k <= 40; ++k) {
            long long sk = pow(L, 1.0 / k);
            while (true) {
                int128 cur = 1;
                for(int p=0; p<k; ++p) cur *= (sk + 1);
                if (cur <= L) sk++;
                else break;
            }
            while (sk > 1) {
                int128 cur = 1;
                for(int p=0; p<k; ++p) cur *= sk;
                if (cur > L) sk--;
                else break;
            }
            if (sk <= 1) break;
            X = (X * (sk % MOD)) % MOD;
        }

        long long r_sum = sum(L, R);
        long long term = (r_sum * X) % MOD;
        tot = (tot + term) % MOD;
    }

    cout << (long long)tot << endl;

    return 0;
}
0