結果

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

ソースコード

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 コード 7: N=1 の時だけWA
ll nosimple_wa7(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);
        
        // --- バグ: i=1 の処理に不要な n > 1 条件を追加 ---
        if(i==1) {
            // N=1 のとき、 n > 1 が false になるため、
            // ans += (up-down) (つまり ans += 1) が実行されない
            if (n > 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);
            ll term = (b - 1 + big2) % big2;
            term = (term * inv) % big2;
            term = (a * term) % big2;
            ans = (ans + term) % big2;
        }
        temp=n/(i+1);
    }
    
    // N=1 の場合、temp=0 なのでこのループは実行されない
    rep(i,1,temp+1){
        ans = (ans + modpow(n/i, i, big2)) % big2;
    }
    
    // N=1 の場合、ans は 0 のまま返される (正解は 1)
    return (ans % big2 + big2) % big2;
}

int main(){
    ll N;
    cin >> N;
    // N=1 を入力すると 0 (WA)
    // N=2 を入力すると 3 (AC)
    // N=4 を入力すると 10 (AC)
    cout << nosimple_wa7(N) << endl; 
}
0