結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー takuma saito
提出日時 2026-04-18 20:55:03
言語 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
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 2,318 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,826 ms
コンパイル使用メモリ 343,232 KB
実行使用メモリ 27,772 KB
最終ジャッジ日時 2026-04-18 20:55:11
合計ジャッジ時間 4,234 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

const long long M = 998244353;

long long pw(long long b, long long e) {
    long long r = 1;
    b %= M;
    while (e > 0) {
        if (e % 2 == 1) r = r * b % M;
        b = b * b % M;
        e /= 2;
    }
    return r;
}

long long sqt(long long x) {
    if (x == 0) return 0;
    long long r = sqrt(x);
    while ((__int128_t)(r + 1) * (r + 1) <= x) r++;
    while ((__int128_t)r * r > x) r--;
    return r;
}

long long F(long long n) {
    if (n == 0) return 0;
    long long m = sqt(n);
    long long k = (m - 1) % M;
    static long long i2 = pw(2, M - 2), i6 = pw(6, M - 2), i30 = pw(30, M - 2);
    long long s2 = k * (k + 1) % M * (2 * k + 1) % M * i6 % M;
    long long s3 = k * (k + 1) % M * i2 % M;
    s3 = s3 * s3 % M;
    long long py = (3 * k % M * k % M + 3 * k % M - 1 + M) % M;
    long long s4 = k * (k + 1) % M * (2 * k + 1) % M * py % M * i30 % M;
    long long a = (2 * s4 % M + 3 * s3 % M + s2) % M;
    long long mm = m % M, nn = n % M, md = mm * mm % M;
    long long s = (nn - md + 1 + M) % M, av = (md + nn) % M;
    long long b = s * av % M * i2 % M * mm % M;
    return (a + b) % M;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long N;
    if (!(cin >> N)) return 0;
    vector<pair<long long, long long>> AA;
    const int MX = 1000005;
    vector<long long> iv(MX);
    iv[1] = 1;
    for (int i = 2; i < MX; i++) iv[i] = M - M / i * iv[M % i] % M;
    auto giv = [&](long long v) { return v < MX ? iv[v] : pw(v, M - 2); };
    for (int k = 3; k <= 62; ++k) {
        for (long long y = 2; ; ++y) {
            __int128_t p = 1;
            for (int i = 0; i < k; ++i) { p *= y; if (p > N) break; }
            if (p > N) break;
            AA.push_back({(long long)p, (y % M) * giv(y - 1) % M});
        }
    }
    sort(AA.begin(), AA.end());
    long long ans = 0, L = 1, v3 = 1;
    int i = 0, E = AA.size();
    while (i < E) {
        long long x = AA[i].first;
        if (L < x) {
            ans = (ans + v3 * ((F(x - 1) - F(L - 1) + M) % M)) % M;
            L = x;
        }
        while (i < E && AA[i].first == x) {
            v3 = v3 * AA[i].second % M;
            i++;
        }
    }
    if (L <= N) ans = (ans + v3 * ((F(N) - F(L - 1) + M) % M)) % M;
    cout << ans << endl;
    return 0;
}
0