結果

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

ソースコード

diff #
raw source code 

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

const long long MOD = 998244353;
//kurikaesi
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = res * base % MOD;
        base = base * base % MOD;
        exp /= 2;
    }
    return res;
}

long long sqrtt(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 = sqrtt(n);
    long long k = (m - 1) % MOD;
    
    static long long inv2 = power(2, MOD - 2);
    static long long inv6 = power(6, MOD - 2);
    static long long inv30 = power(30, MOD - 2);
    
    long long S2 = k * (k + 1) % MOD * (2 * k + 1) % MOD * inv6 % MOD;
    long long S3 = k * (k + 1) % MOD * inv2 % MOD;
    S3 = S3 * S3 % MOD;
    long long poly = (3 * k % MOD * k % MOD + 3 * k % MOD - 1 + MOD) % MOD;
    long long S4 = k * (k + 1) % MOD * (2 * k + 1) % MOD * poly % MOD * inv30 % MOD;
    
    long long A = (2 * S4 % MOD + 3 * S3 % MOD + S2) % MOD;
    
    long long modm = m % MOD;
    long long modn = n % MOD;
    long long modd = modm * modm % MOD;
    
    long long S = (modn - modd + 1 + MOD) % MOD;
    long long avg = (modd + modn) % MOD;
    
    long long B = S * avg % MOD * inv2 % MOD * modm % MOD;
    
    return (A + B) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N;
    cin >> N;
    
    vector<long long> X;
    X.push_back(1);
    for (int k = 3; k <= 62; ++k) {
        for (long long y = 2; ; ++y) {
            __int128_t p = 1;
            bool ok = true;
            for (int i = 0; i < k; ++i) {
                p *= y;
                if (p > N) {
                    ok = false;
                    break;
                }
            }
            if (!ok) break;
            X.push_back((long long)p);
        }
    }
    X.push_back(N + 1);
    
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    
    long long R_val[65];
    for (int k = 3; k <= 62; ++k) R_val[k] = 1;
    
    long long ans = 0;
    
    for (size_t i = 0; i < X.size() - 1; ++i) {
        long long L = X[i];
        long long R = X[i+1] - 1;
        if (L > R) continue;
        
        long long v3 = 1;
        
        for (int k = 3; k <= 62; ++k) {
            while (true) {
                __int128_t p = 1;
                bool ok = false;
                long long vall = R_val[k] + 1;
                for (int j = 0; j < k; ++j) {
                    p *= vall;
                    if (p > L) {
                        ok = true;
                        break;
                    }
                }
                if (!ok) {
                    R_val[k]++;
                } else {
                    break;
                }
            }
            if (R_val[k] == 1) break;
            
            v3 = v3 * (R_val[k] % MOD) % MOD;
        }
        
        long long FF = (F(R) - F(L - 1) + MOD) % MOD;
        ans = (ans + v3 * FF % MOD) % MOD;
    }
    
    cout << ans << endl;
    
    return 0;
}
0