結果
| 問題 | No.3364 Push_back Operation |
| コンテスト | |
| ユーザー |
 2251799813685248
|
| 提出日時 | 2026-06-01 16:49:15 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 129 ms / 2,000 ms |
| コード長 | 9,026 bytes |
| 記録 | |
| コンパイル時間 | 1,694 ms |
| コンパイル使用メモリ | 227,820 KB |
| 実行使用メモリ | 28,024 KB |
| 最終ジャッジ日時 | 2026-06-01 16:49:21 |
| 合計ジャッジ時間 | 5,682 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 53 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <functional>
#include <random>
#include <bitset>
#include <unistd.h>
using namespace std;
using ll = long long;
using lll = __int128_t;
using ull = unsigned long long;
using ld = long double;
using pii = array<int,2>;
using pll = array<ll,2>;
using plll = array<lll,2>;
#define vall(A) A.begin(), A.end()
template<typename T> inline void vin(T& A){for (int i = 0, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void vout(const T& A){for (int i = 0, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void vout2d(const T& A){for (int i = 0, H = A.size(); i < H; i++){vout(A[i]);}}
template<typename T> inline void adjvin(T& A){for (int i = 1, sz = A.size(); i < sz; i++){cin >> A[i];}}
template<typename T> inline void adjvout(const T& A){for (int i = 1, sz = A.size(); i < sz; i++){cout << A[i] << " \n"[i == sz-1];}}
template<typename T> inline void adjvout2d(const T& A){for (int i = 1, H = A.size(); i < H; i++){adjvout(A[i]);}}
template<typename T> inline bool btest(T K, int i){return K&(1ull<<i);}
inline void print(){cout << "\n";}
inline void printflush(){cout << endl;}
template<typename T, typename... U> inline void print(T obj1, U... obj2){cout << (obj1) << " "; print(obj2...);}
template<typename T, typename... U> inline void printflush(T obj1, U... obj2){cout << (obj1) << " "; printflush(obj2...);}
constexpr ll pow2ll[63] = {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,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904};
constexpr ll pow10ll[19] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
constexpr ll di[4] = {0,1,0,-1};
constexpr ll di8[8] = {0,1,1,1,0,-1,-1,-1};
constexpr ll dj[4] = {1,0,-1,0};
constexpr ll dj8[8] = {1,1,0,-1,-1,-1,0,1};
#ifndef MATH_FUNCTION_HPP_
#define MATH_FUNCTION_HPP_
#include <array>
#include <cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。
constexpr ll modpow(ll a, ull b, const ll m){
ll t = a%m;
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に関して線形時間で計算できる。
constexpr ll powll(ll a, ull n){
ll r = 1;
for (ull i = 1; i <= n; i++){
r *= a;
}
return r;
}
/// @brief floor(sqrt(N))を返す
constexpr ll isqrt(ll N){
if (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;
}
else{return 0;}
}
/// @brief floor(log_a(L))を返す
constexpr ll ilog(ll a, ll L){
__int128_t t = 1;
ll ans = 0;
while (t <= L){
ans++;
t *= a;
}
return ans-1;
}
/// @brief 有理数のfloorを求める
constexpr inline ll floor2(ll y, ll x){
if ((x^y) > 0){
x = abs(x);
y = abs(y);
return y/x;
}
else if ((x^y) < 0){
x = abs(x);
y = abs(y);
return -((y+x-1)/x);
}
else{
return y/x;
}
}
/// @brief 有理数のceilを求める
constexpr inline ll ceil2(ll y, ll x){
if ((x^y) > 0){
x = abs(x);
y = abs(y);
return (y+x-1)/x;
}
else if ((x^y) < 0){
x = abs(x);
y = abs(y);
return -(y/x);
}
else{
return y/x;
}
}
/// @brief 一次不定方程式ax+by=gcd(a,b)の解を1つ見つける
/// @param a `a>=0`である必要がある
/// @param b `b>=0`である必要がある
/// @return {x,y,gcd(a,b)}
template<typename T>
constexpr array<T,3> axby1(T a, T b){
T x = 1, y = 0;
T z = 0, w = 1;
T tmp = 0;
while (b){
T p = a/b, q = a%b;
tmp = x - y * p; x = y; y = tmp;
tmp = z - w * p; z = w; w = tmp;
a = b; b = q;
}
return {x, z, a};
}
/// @brief 1/a mod Mを求める
template<typename T, typename U>
constexpr T inverse_mod(T a, U M){
auto temp = axby1(a,(T)M);
assert(temp[2] == 1);
return (M+temp[0])%M;
}
/// @brief sqrt(a) mod Mを求める。ないなら-1が返される。
template<ll M>
constexpr ll cipolla(ll a){
a %= M;
if (M == 2) return a;
if (a == 0) return 0;
ll z = (M-1)/2;
if (modpow(a, z, M) != 1){return -1;}
int b = 0;
while (modpow((b*b+M-a)%M, z, M) == 1){
b++;
}
array<ll,2> x{1,0};
array<ll,2> y{b, 1};
ll w = (b*b+M-a)%M;
z++;
while (z){
if (z&1){
ll temp = x[0];
x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
if (x[0] >= M){x[0] -= M;}
x[1] = temp*y[1]%M+x[1]*y[0]%M;
if (x[1] >= M){x[1] -= M;}
}
ll temp = y[0];
y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
if (y[0] >= M){y[0] -= M;}
y[1] = 2*temp*y[1]%M;
z >>= 1;
}
return x[0];
}
ll cipolla(ll a, const ll M){
a %= M;
if (M == 2) return a;
if (a == 0) return 0;
ll z = (M-1)/2;
if (modpow(a, z, M) != 1){return -1;}
int b = 0;
while (modpow((b*b+M-a)%M, z, M) == 1){
b++;
}
array<ll,2> x{1,0};
array<ll,2> y{b, 1};
ll w = (b*b+M-a)%M;
z++;
while (z){
if (z&1){
ll temp = x[0];
x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
if (x[0] >= M){x[0] -= M;}
x[1] = temp*y[1]%M+x[1]*y[0]%M;
if (x[1] >= M){x[1] -= M;}
}
ll temp = y[0];
y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
if (y[0] >= M){y[0] -= M;}
y[1] = 2*temp*y[1]%M;
z >>= 1;
}
return x[0];
}
/// @brief x以下の最大の2冪を返す。0は0が返る。
constexpr int lowerpow2(ull x){
if (x == 0){return 0;}
return 1ull<<(63-__builtin_clzll(x));
}
/// @brief x以上の最小の2冪を返す。0は0が返る。
constexpr int upperpow2(ull x){
if (x == 0){return 0;}
if (x == 1){return 1;}
return 1ull<<(64-__builtin_clzll(x-1));
}
#endif /* MATH_FUNCTION_HPP_ */
#ifndef QUOTIENTS_HPP_
#define QUOTIENTS_HPP_
#include <vector>
#include <array>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
/// @brief 1<=x<=M の範囲におけるN/xの商を列挙する。
vector<array<ll,3>> enumerate_quotient(ll N, ll M){
vector<array<ll,3>> ret;
if (N == 0){
ret.push_back({0,1,M});
return ret;
}
ll k0 = sqrtl(N)-100;
k0 = max(0ll, k0);
ll k0r = sqrtl(N)+100;
while (k0r*(k0r+1) <= N){
k0r++;
}
while (k0r-k0 > 1){
ll mid = (k0+k0r)/2;
if (mid*(mid+1) <= N){
k0 = mid;
}
else{
k0r = mid;
}
}
for (ll k = k0; k >= 0; k--){
ret.push_back({k, N/(k+1)+1, min(M, k > 0 ? N/k : M)});
if (ret.back()[1] > ret.back()[2]){
ret.pop_back();
break;
}
}
reverse(ret.begin(), ret.end());
for (ll x = min(M, N/(k0+1)); x >= 1; x--){
ret.push_back({N/x, x,x});
}
return ret;
}
#endif /* QUOTIENTS_HPP_ */
constexpr ll mod = 998244353;
//factorialncr<998244353> nCr(1000000);
void solve(){
ll N;
cin >> N;
auto quotients = enumerate_quotient(N,N);
ll ans = 0;
for (auto& q : quotients){
if (q[2] == q[1]){
ans += modpow(q[0], q[1], 998244353);
ans %= 998244353;
}
else{
auto f = [](ll a, ll n){return a == 1 ? (n+1)%998244353 : (modpow(a,n+1,998244353)+998244352)*inverse_mod(a-1, 998244353)%998244353;};
ans += f(q[0], q[2])-f(q[0],q[1]-1);
ans %= 998244353;
}
}
print((998244353+ans)%998244353);
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll T = 1;
//cin >> T;
while (T--){
solve();
}
}