結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 剰余
const int MOD = 998244353;
using ll = long long;

// べき乗計算
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// 逆元計算 (フェルマーの小定理)
ll mod_inv(ll n) {
    return power(n, MOD - 2);
}

// --------------------------------------------------
// 前計算: メビウス関数 \mu(d)
// --------------------------------------------------
ll MAX_MU_LIMIT;
vector<int> mu;

void sieve_mu(ll limit) {
    limit = min(limit, (ll)320000); 
    MAX_MU_LIMIT = limit;
    mu.resize(limit + 1);
    vector<int> min_prime(limit + 1, 0);
    vector<int> primes;

    mu[1] = 1;
    for (int i = 2; i <= limit; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if (p > min_prime[i] || (ll)i * p > limit) break;
            min_prime[i * p] = p;
            if (p == min_prime[i]) {
                mu[i * p] = 0;
            } else {
                mu[i * p] = -mu[i];
            }
        }
    }
}

// --------------------------------------------------
// T の約数 L のベキ乗和の総和を O(\sqrt{T_{max}} \log N) で計算する関数
// \sum_{T=1}^{T_{max}} \sum_{L \mid T} Y^L
// --------------------------------------------------
ll sum_L_powers_total(ll T_max, ll Y) {
    ll total_sum = 0;
    if (T_max == 0 || Y == 0) return 0;
    
    // Lに関する総和を \lfloor T_{max}/L \rfloor が一定になる区間に分割 (O(\sqrt{T_{max}}))
    // このとき、\lfloor T_{max}/L \rfloor は、T=L*kのkの最大値に相当する
    for (ll L_start = 1; L_start <= T_max; ) {
        ll count = T_max / L_start; // T=L*k の k の最大値
        ll L_end = T_max / count; 
        
        // 区間 [L_start, L_end] での Y^L の総和を等比数列の和で計算 (O(\log N))
        ll sum_L = 0;
        if (Y == 1) {
            // Y=1 の場合: L_end - L_start + 1
            sum_L = (L_end - L_start + 1) % MOD;
        } else {
            // Y > 1 の場合: 等比数列の和
            ll start_term = power(Y, L_start);
            ll num_terms = L_end - L_start + 1;
            ll ratio_power = power(Y, num_terms);
            
            ll numerator = (ratio_power - 1 + MOD) % MOD;
            ll denominator_inv = mod_inv(Y - 1); 
            
            ll geometric_sum = (start_term * numerator) % MOD;
            geometric_sum = (geometric_sum * denominator_inv) % MOD;
            sum_L = geometric_sum;
        }

        // 寄与: count * \sum_{L=L_{start}}^{L_{end}} Y^L
        // count は T が L の倍数となる個数
        ll term = (count % MOD) * sum_L % MOD;
        total_sum = (total_sum + term) % MOD;

        L_start = L_end + 1;
    }

    return total_sum;
}


// --------------------------------------------------
// f(T) = \sum_{d=1}^{\lfloor N/T \rfloor} \mu(d) \left( \sum_{L \mid T} \left( \lfloor \frac{\lfloor N/T \rfloor}{d} \rfloor \right)^L \right) の累積和を計算
// G(T_max) = \sum_{T=1}^{T_{max}} f(T)
// --------------------------------------------------
ll G(ll N, ll T_max) {
    if (T_max == 0) return 0;

    ll total_sum = 0;

    // Tに関する総和を \lfloor N/T \rfloor = X が一定な区間に分割 (O(\sqrt{N}))
    // この区間 T \in [T_start, T_end] の総和は S_X
    for (ll T_start = 1; T_start <= T_max; ) {
        ll X = N / T_start;
        ll T_end = min(T_max, N / X); // 区間の終点は T_max で打ち切り

        // dに関する総和: \sum_{d=1}^{X} \mu(d) \cdot S_{T}(d) 
        ll current_block_sum = 0;
        
        // d の総和の上限は X だが、\mu(d) の前計算は SQRT_N まで
        ll d_limit = min(X, MAX_MU_LIMIT); 

        for (ll d = 1; d <= d_limit; ++d) {
            if (mu[d] == 0) continue;

            ll Y = X / d; // \lfloor X/d \rfloor

            // T_startからT_endまでの区間での \sum_{T} \sum_{L \mid T} Y^L の計算
            // sum_L_powers_total(T_max, Y) = \sum_{T=1}^{T_{max}} \sum_{L \mid T} Y^L
            // T_end の累積和から T_start-1 の累積和を引く (差分計算)
            
            // \sum_{T=T_{start}}^{T_{end}} \sum_{L \mid T} Y^L 
            ll sum_T_L_end = sum_L_powers_total(T_end, Y);
            ll sum_T_L_start_minus_1 = sum_L_powers_total(T_start - 1, Y);
            
            ll sum_T_L = (sum_T_L_end - sum_T_L_start_minus_1 + MOD) % MOD;

            ll term = (mu[d] == 1) ? sum_T_L : (MOD - sum_T_L) % MOD;
            current_block_sum = (current_block_sum + term) % MOD;
        }

        total_sum = (total_sum + current_block_sum) % MOD;
        T_start = T_end + 1;
    }

    return total_sum;
}


// --------------------------------------------------
// メイン関数
// --------------------------------------------------
void solve() {
    ll N;
    if (!(cin >> N)) return;

    ll SQRT_N = sqrt(N);
    sieve_mu(SQRT_N);

    // 求める総数は G(N) = \sum_{T=1}^{N} f(T)
    ll result = G(N, N);

    cout << result << endl;
}

int main() {
    // 高速化のために入出力を解除
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
    return 0;
}
0