結果

問題 No.3364 Push_back Operation
コンテスト
ユーザー ponjuice
提出日時 2025-11-17 21:39:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,554 bytes
コンパイル時間 3,080 ms
コンパイル使用メモリ 276,444 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-11-17 21:39:30
合計ジャッジ時間 7,378 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i <(b); i++)
#define all(a) begin(a),end(a)
#define sz(a) ssize(a)
bool chmin(auto& a,auto b){return a > b ? a = b,1 : 0;}
bool chmax(auto& a,auto b){return a < b ? a = b,1 : 0;}
const ll mod = 998244353;

// 1 -> n
// 2 -> (n/2)^2
// 3 -> (n/3)^3
// sqrt(n) までは計算する
// それ以降は k ^ (a) + k ^ (a+1) + ... + k ^ (b)  (a,b は適切な値) の形に分解して計算する
// O(sqrt(n)log(n)) ぐらい？
// k^a + k^(a+1) + ... + k^b = k^a * (k^(b-a+1) - 1) / (k-1)

ll mod_pow(ll a, ll b) {
    ll res = 1;
    a %= mod;
    while(b > 0) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    ll n;
    cin >> n;

    if(n < 1000'000) {
        ll ans = 0;
        rep(i,1,n+1) {
            ans = (ans + mod_pow(n/i, i)) % mod;
        }
        cout << ans << endl;
        return 0;
    }

    ll ans = 0;
    ll m = sqrt(n);
    rep(i,1,m) {
        ans += mod_pow(n/i, i);
    }
    ll last = m;
    for(ll k = m; k >= 1; k--) {
        ll a = n / (k + 1) + 1;
        ll b = n / k;
        a = max(a, last);
        if(a > b) continue;
        ll len = b - a + 1;
        ll first = mod_pow(k, a);
        ll mult = (mod_pow(k, len) - 1 + mod) % mod * mod_pow(k - 1, mod - 2) % mod;
        ans = (ans + first * mult) % mod;
    }
    cout << ans % mod << endl;
}
0