結果

問題 No.3364 Push_back Operation
コンテスト
ユーザー fken_prime_57
提出日時 2025-10-25 17:40:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,142 bytes
コンパイル時間 800 ms
コンパイル使用メモリ 104,356 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-11-17 20:32:35
合計ジャッジ時間 4,324 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 1 TLE * 1 -- * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // cin, cout
#include <vector>   // vector
#include <cmath>    // (このコードでは不要だが一般的に使う)
#include <limits>   // (このコードでは不要だが一般的に使う)

using namespace std;
using ll = long long;
#define rep(i,x,lim) for(ll i = (x);i < (ll)(lim);i++)
const ll big2 = 998244353;

// 正しい modpow
ll modpow(ll x, ll n, ll m) {
    ll res = 1;
    x %= m;
    while (n > 0) {
        if (n & 1) res = (res * x) % m;
        x = (x * x) % m;
        n >>= 1;
    }
    return res;
}

// --- バグ: mod を取らない単純な pow を実装しようとした ---
ll naive_pow(ll k, ll i) {
    ll res = 1;
    for (ll j = 0; j < i; j++) {
        // k=2, i=100 の時点でもう long long を超える
        // N=10^12 なら i は 3*10^5 になるため、即座にオーバーフロー
        
        // オーバーフローチェック (簡易)
        if (k > 0 && res > numeric_limits<ll>::max() / k) {
             // 本来はここでエラー処理だが、競技プログラミングだと無視されがち
             // 結果、オーバーフローして負の値などになる
        }
        res *= k; 
    }
    return res;
}
// --------------------------------------------------------

ll nosimple_wa4(ll n){
    ll ans = 0;
    ll temp = n;
    for(ll i=1;i*i<=n;i++){
        ll k = i;
        ll up=n/k;
        ll down=n/(k+1);
        if(k==1) ans = (ans + (up-down)) % big2;
        else {
            ll a = modpow(k, down + 1, big2);
            ll b = modpow(k, up - down, big2);
            ll inv = modpow(k - 1, big2 - 2, big2);
            ans = (ans + a * (b - 1 + big2) % big2 * inv % big2) % big2;
        }
        temp = n / (i + 1);
    }
    
    rep(i,1,temp+1){
        ll k = n/i;
        // --- バグ: modpow ではなく、オーバーフローする naive_pow を使った ---
        ans = (ans + naive_pow(k, i)) % big2; 
        // -------------------------------------------------------------
    }
    return (ans % big2 + big2) % big2;
}

int main(){
    ll N;
    cin >> N;
    cout << nosimple_wa4(N) << endl; 
}
0