結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>


using namespace std;
#define ll long long
#define MOD 998244353LL
#define ld long double
#define INF 2251799813685248
#define vall(A) A.begin(),A.end()
#define gridinput(vv,H,W) for (ll i = 0; i < H; i++){string T; cin >> T; for(ll j = 0; j < W; j++){vv[i][j] = {T[j]};}}
#define adjustedgridinput(vv,H,W) for (ll i = 1; i <= H; i++){string T; cin >> T; for(ll j = 1; j <= W; j++){vv[i][j] = {T[j-1]};}}
#define vin(A) for (ll i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}
#define vout(A) for(ll i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define adjustedvin(A) for (ll i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}
#define adjustedvout(A) for(ll i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}
#define vout2d(A,H,W) for (ll i = 0; i < H; i++){for (ll j = 0; j < W; j++){cout << A[i][j] << " \n"[j==W-1];}}
#define encode(i,j) ((i)<<32)+j
#define decode(v,w) (w ? (v)%4294967296 : (v)>>32)
vector<ll> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296};
vector<ll> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};

/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
/// @param a 
/// @param b 
/// @param m 
/// @return a^b%m
ll modpow(ll a, ll b, ll m){
    ll t = a;
    ll ans = 1;
    while (b > 0){
        if (b%2){
            ans = (ans*t)%m;
        }
        b /= 2;
        t = (t*t)%m;
    }
    return ans;
}

/// @brief a^nを返す。bに関して線形時間で計算できる。
/// @param a 
/// @param n
/// @param m 
/// @return a^n
ll powll(ll a, ll n){
    ll r = 1;
    for (ll i = 1; i <= n; i++){
        r *= a;
    }
    return r;
}


/// @brief 一次不定方程式ax+by=1の解を1つ見つける
/// @param a 
/// @param b 
/// @return {x,y}
pair<ll,ll> axby1(ll a, ll b){
    if (a == 1 or b == 1){
        if (a == 1){
            return {1-b,1};
        }
        else{
            return {1,1-a};
        }
    }
    else if (a>b){
        auto p = axby1(a%b, b);
        return {p.first, p.second - p.first*(a/b)};
    }
    else{
        swap(a,b);
        auto p = axby1(a%b, b);
        return {p.second - p.first*(a/b), p.first};
    }
}

/// @brief 1/a mod Mを求める
/// @param a 
/// @param M 
/// @return 1/a mod M
ll inverse_mod(ll a, ll M){
    if (__gcd(a,M) != 1){
        return -1;
    }
    return (M+axby1(a,M).first%M)%M;
}



/// @brief sum[i=1 ~ i=N] (floor(N/i))^i を計算する
/// @param N 
/// @param M 
/// @param a 
/// @param b 
/// @return 
ll inv_floor_sum(ll N){
    auto floorsqrt = [](ll N){
        ll ok = 1;
        ll ng = min(N,2000000000LL);
        while (ng - ok >= 2){
            ll mid = (ok+ng)/2;
            if (mid*mid <= N){
                ok = mid;
            }
            else{
                ng = mid;
            }
        }
        return ok;
    };
    



    auto sum = [&](ll r, ll a, ll b){
        if (r == 1){return b-a;}
        else{
            return ((modpow(r,a+1,MOD)*inverse_mod(r-1,MOD))%MOD * (modpow(r,b-a,MOD)-1))%MOD;
        }
    };


    ll ans = 0;
    ll rootN = floorl(sqrtl((ld)N));

    //それ以外の場合は主客転倒を行う

    for (ll i = 1; i <= N/rootN; i++){//最初の方をそのまま足す。
        ans += modpow(N/i,i,MOD);
        ans %= MOD;
    }
    for (ll i = rootN-1; i >= 1; i--){
        ans += sum(i,N/(i+1),N/i);
        ans %= MOD;
    }

    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll N;
    cin >> N;
    __int128_t M = N;
    //if (N > pow10ll[8]){assert(false);}
    cout << (MOD+inv_floor_sum(M)%MOD)%MOD << "\n";
    //for (ll T = N; T <= N; T++){
    //ll ans2 = 0;
    //for (ll i = 1; i <= T; i++){
    //    ans2 += (modpow(T/i,i,MOD));
    //    ans2 %= MOD;
    //}
    //ll ans1 = (MOD+inv_floor_sum(T)%MOD)%MOD;
    //if (ans1 == ans2){continue;}
    //cout << T << "\n";
    //cout << ans1 << "\n";
    //cout << ans2 << "\n";
    //}
}
0