結果

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

ソースコード

diff # 

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

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

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;
}

// WA コード 5: mod の取り忘れ
ll nosimple_wa5(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) {
             // --- バグ: (up-down) が巨大な場合に % を忘れる ---
             // ans += (up-down); 
             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);
            
            // --- バグ: (b - 1) が負になるケース (b=0) で +big2 を忘れている ---
            ll term = (b - 1) % big2; 
            // ll term = (b - 1 + big2) % big2; // ← 正解
            
            // --- バグ: 途中の % を忘れると long long を超える ---
            term = (term * inv); // % big2 が必要
            term = (a * term);   // % big2 が必要
            
            ans += term; // % big2 が必要
            
            // 正しくはこう
            // ll term = (b - 1 + big2) % big2; 
            // term = (term * inv) % big2;
            // term = (a * term) % big2;
            // ans = (ans + term) % big2;
        }
        temp = n / (i + 1);
    }
    
    rep(i,1,temp+1){
        ll k = n/i;
        // --- バグ: ここでも ans += ... % big2 とすべき ---
        ans += modpow(k, i, big2);
        // ans = (ans + modpow(k, i, big2)) % big2; // ← 正解
        // ----------------------------------------
    }
    return (ans % big2 + big2) % big2;
}

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