結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <deque>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = atcoder::modint998244353;
// #include <bits/stdc++.h> // 重複しているのでコメントアウト
// using namespace std; // 重複
using lint = ll;
lint MOD = 998244353;
//#define //_GLIBCXX_DEBUG

template<typename T>
T modpow(T a, T b, T mod=998244353) {
    T res = 1;
    // ★重要: 'a' を % mod してからループを開始する
    a = (a % mod + mod) % mod; 
    while (b > 0) {
        if (b&1) (res *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}

template<typename T>
T modinv(T n, T mod=998244353) {
    // ★重要: 'n' を % mod してから開始する
    n = (n % mod + mod) % mod; 
    T m = mod, u = 1, v = 0;
    while (m) {
        T t = n / m; // ★バグ修正: long long t ではなく T t
        n -= t * m; swap(n, m);
        u -= t * v; swap(u, v);
    }
    // ★重要: gcd(n, mod) != 1 のチェック
    if (n != 1) return -1; // 逆元なし（エラー）
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

mint simple(ll N){
    mint ans=0;
    ll uplimit=-1;
    for(ll i=1;i*i<=N;i++){
        ll up=N/i;
        ll down=N/(i+1);
        mint a=mint(i).pow(down+1);
        mint b=mint(i).pow(up-down);
        
        // i は k = N/L の値
        mint k = i;
        if(k == 1) ans += up-down; // k=1 (modも考慮)
        else{
            ans += a * ((b-1) / (k-1));
        }
        uplimit = N/(i+1);
    }
    for(ll i=1;i<=uplimit;i++){
        // i は L の値
        // N/i は k の値 (MOD+1 になりうるが、割り算はしない)
        ans += mint(N/i).pow(i);
    }
    return ans;
}

ll b2(ll n){
    lint ans = 0;
    for (lint i = 1; i <= n; i++) {
        lint a = n/i; // k の値 (10^11 オーダーになりうる)
        lint r = n/a;
        lint len = r-i+1;

        // ★★★ 致命的なバグ ★★★
        // a-1 が 10^11 オーダーのまま modinv に渡され、
        // modinv 内部で long long オーバーフローが発生する。
        //
        // 修正版：
        // lint a_mod = a % MOD;
        // if (a_mod != 1) {
        //   lint a_minus_1_mod = (a_mod - 1 + MOD) % MOD;
        //   ans += modpow(a_mod, i) * (modpow(a_mod, len)-1+MOD)%MOD * modinv(a_minus_1_mod);
        // } else { ... }
        //
        // ★★★ 元のバグありコード ★★★
        if (a%MOD != 1) ans += modpow(a, i)*(modpow(a, len)-1+MOD)%MOD*modinv(a-1), ans %= MOD;
        else ans += len;

        i = r;
    }
    return ans%MOD;
}


int main() {
    lint n;
    cin >> n;
    cout << b2(n) << '\n';
}
0