結果
| 問題 | No.3651 K-th Sum of Divisors |
| コンテスト | |
| ユーザー |
 siganai
|
| 提出日時 | 2026-08-30 10:45:42 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 22 ms / 2,000 ms |
| + 352µs | |
| コード長 | 21,638 bytes |
| 記録 | |
| コンパイル時間 | 1,880 ms |
| コンパイル使用メモリ | 244,164 KB |
| 実行使用メモリ | 15,104 KB |
| 最終ジャッジ日時 | 2026-08-30 10:45:53 |
| 合計ジャッジ時間 | 5,663 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 55 |
ソースコード
#line 1 "main.cpp"
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.hpp>
#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (static_cast<void>(0))
#endif
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vul = vector<ull>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vs = vector<string>;
template<class T> using pq = priority_queue<T,vector<T>, greater<T>>;
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(a,b,c,name,...) name
#define rep1(n) for (ll UNUSED_NUMBER = 0; UNUSED_NUMBER < (n); ++UNUSED_NUMBER)
#define rep2(i, n) for (ll i = 0; i < (n); ++i)
#define rep3(i, a, b) for (ll i = (a); i < (b); ++i)
#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n) - 1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (b) - 1;i >= (a);i--)
#define rrep4(i,a,b,c) for(ll i = (a) + (((b)-(a)-1) / (c) - (((b)-(a)-1) % (c) && (((b)-(a)-1) ^ c) < 0)) * (c);i >= (a);i -= c)
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define all1(i) begin(i) , end(i)
#define all2(i,a) begin(i) , begin(i) + a
#define all3(i,a,b) begin(i) + a , begin(i) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__),0LL)
template<class T> bool chmin(T &a, const T &b){ if(a > b){ a = b; return 1; } else return 0; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } else return 0; }
template<class T> auto min(const T& a){return *min_element(all(a));}
template<class T> auto max(const T& a){return *max_element(all(a));}
template<class... Ts> void in(Ts&... t);
#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; in(__VA_ARGS__)
#define VEC(type, name, size) vector<type> name(size); in(name)
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); in(name)
ll intpow(ll a, ll b){ll ans = 1; while(b){if(b & 1) ans *= a; a *= a; b /= 2;} return ans;}
ll modpow(ll a, ll b, ll p){ ll ans = 1 % p; a %= p;if(a < 0) a += p;while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
bool is_clamp(ll val,ll low,ll high) {return low <= val && val < high;}
void Yes() {cout << "Yes\n";return;}
void No() {cout << "No\n";return;}
void YES() {cout << "YES\n";return;}
void NO() {cout << "NO\n";return;}
template <typename U,typename T>
U floor(U a, T b) {return a / b - (a % b && (a ^ b) < 0);}
// ceil(x,y) = floor(x+y-1,y)なのでx+y-1がoverflowする可能性あり
template <typename U,typename T>
U ceil(U x, T y) {return floor(x + y - 1, y);}
template <typename U,typename T>
T bmod(U x, T y) {return x - y * floor(x, y);}
template <typename U,typename T>
pair<U, T> divmod(U x, T y) {U q = floor(x, y);return {q, x - q * y};}
namespace IO{
#define VOID(a) decltype(void(a))
struct setting{ setting(){cin.tie(nullptr); ios::sync_with_stdio(false);fixed(cout); cout.precision(15);}} setting;
template<int I> struct P : P<I-1>{};
template<> struct P<0>{};
template<class T> void i(T& t){ i(t, P<3>{}); }
void i(vector<bool>::reference t, P<3>){ int a; i(a); t = a; }
template<class T> auto i(T& t, P<2>) -> VOID(cin >> t){ cin >> t; }
template<class T> auto i(T& t, P<1>) -> VOID(begin(t)){ for(auto&& x : t) i(x); }
template<class T, size_t... idx> void ituple(T& t, index_sequence<idx...>){in(get<idx>(t)...);}
template<class T> auto i(T& t, P<0>) -> VOID(tuple_size<T>{}){ituple(t, make_index_sequence<tuple_size<T>::value>{});}
#undef VOID
}
#define unpack(a) (void)initializer_list<int>{(a, 0)...}
template<class... Ts> void in(Ts&... t){ unpack(IO :: i(t)); }
#undef unpack
constexpr long double PI = 3.141592653589793238462643383279L;
template <class F> struct REC {
F f;
REC(F &&f_) : f(forward<F>(f_)) {}
template <class... Args> auto operator()(Args &&...args) const { return f(*this, forward<Args>(args)...); }};
constexpr int mod = 998244353;
//constexpr int mod = 1000000007;
#line 2 "library/modint/Modint.hpp"
template <int mod>
struct Modint{
int x;
Modint():x(0) {}
Modint(long long y): x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
Modint &operator += (const Modint &p) {
if((x += p.x) >= mod) x -= mod;
return *this;}
Modint &operator -= (const Modint &p) {
if ((x += mod - p.x) >= mod) x -= mod;
return *this;}
Modint &operator *= (const Modint &p) {
x = (int)(1LL * x * p.x % mod);
return *this;}
Modint &operator /= (const Modint &p) {
*this *= p.inverse();
return *this;}
Modint operator -() const{return Modint(-x);}
Modint operator +(const Modint &p) const {return Modint(*this) += p;}
Modint operator -(const Modint &p) const {return Modint(*this) -= p;}
Modint operator *(const Modint &p) const {return Modint(*this) *= p;}
Modint operator /(const Modint &p) const {return Modint(*this) /= p;}
friend constexpr Modint operator +(long long lhs, const Modint &rhs) {
return Modint(lhs) + rhs;
}
friend constexpr Modint operator -(long long lhs, const Modint &rhs) {
return Modint(lhs) - rhs;
}
friend constexpr Modint operator *(long long lhs, const Modint &rhs) {
return Modint(lhs) * rhs;
}
friend constexpr Modint operator /(long long lhs, const Modint &rhs) {
return Modint(lhs) / rhs;
}
Modint &operator ++() {if(x == mod - 1) x = 0; else x++; return *this;}
Modint &operator --() {if(x == 0) x = mod - 1; else x--; return *this;}
Modint operator ++(int) {Modint old = *this; ++(*this); return old;}
Modint operator --(int) {Modint old = *this; --(*this); return old;}
bool operator == (const Modint &p) const {return x == p.x;}
bool operator != (const Modint &p) const {return x != p.x;}
Modint inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return Modint(u);}
Modint pow(long long n) const {
Modint ret(1), mul(x);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;}
friend ostream &operator<<(ostream &os, const Modint &p) { return os << p.x; }
friend istream &operator>>(istream &is, Modint &a) {
long long t;
is >> t;
a = Modint<mod>(t);
return (is);
}
int get() const { return x; }
static constexpr int get_mod() {return mod;}
};
#line 102 "main.cpp"
constexpr int M = 100003;
using mint = Modint<M>;
using vm = vector<mint>;
using vvm = vector<vm>;
using vvvm = vector<vvm>;
#line 2 "library/data-structure/unionfind.hpp"
struct unionfind {
public:
unionfind() : _n(0) {}
explicit unionfind(int n) : _n(n), parent_or_size(n, -1) {}
//leaderが返り値
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = find(a), y = find(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return find(a) == find(b);
}
int find(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = find(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[find(a)];
}
vector<vector<int>> groups() {
vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = find(i);
group_size[leader_buf[i]]++;
}
vector<vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
remove_if(result.begin(), result.end(),
[&](const vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
vector<int> parent_or_size;
};
#line 2 "library/graph/graph-template.hpp"
template <typename T>
struct Edge {
int from, to;
T cost;
Edge() = default;
Edge(int _to, T _cost) : from(-1), to(_to), cost(_cost) {}
Edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}
bool operator < (const Edge &a) const { return cost < a.cost; }
bool operator > (const Edge &a) const { return cost > a.cost; }
Edge &operator = (const int &x) {
to = x;
return *this;
}
operator int() const { return to; }
friend ostream& operator<<(ostream &os, const Edge &edge) {
return os << edge.to;
}
};
template <typename T>
using Edges = vector<Edge<T>>;
template <typename T>
using Wgraph = vector<Edges<T>>;
using Ugraph = vector<vector<int>>;
Ugraph uinput(int N, int M = -1, bool is_directed = false, int origin = 1) {
Ugraph g(N);
if (M == -1) M = N - 1;
while(M--) {
int a,b;
cin >> a >> b;
a -= origin, b -= origin;
g[a].push_back(b);
if(!is_directed) g[b].push_back(a);
}
return g;
}
template <typename T>
Wgraph<T> winput(int N, int M = -1, bool is_directed = false,int origin = 1) {
Wgraph<T> g(N);
if (M == -1) M = N - 1;
while(M--) {
int a,b;
T c;
cin >> a >> b >> c;
a -= origin, b -= origin;
g[a].emplace_back(b,c);
if(!is_directed) g[b].emplace_back(a,c);
}
return g;
}
#line 3 "library/tree/HLD.hpp"
template <typename G = vector<vector<int>>>
struct HLD {
private:
void dfs_sz(int root) {
vector<int> vs;
vs.reserve(g.size());
par[root] = -1;
depth[root] = 0;
vector<int> st;
st.push_back(root);
while (!st.empty()) {
int cur = st.back();
st.pop_back();
vs.push_back(cur);
for (int dst : g[cur]) {
if (dst == par[cur]) continue;
par[dst] = cur;
depth[dst] = depth[cur] + 1;
st.push_back(dst);
}
}
for (int i = int(vs.size()) - 1; i >= 0; i--) {
int cur = vs[i];
size[cur] = 1;
int heavy_pos = -1;
int heavy_size = -1;
for (int j = 0; j < int(g[cur].size()); j++) {
int dst = g[cur][j];
if (dst == par[cur]) continue;
size[cur] += size[dst];
if (size[dst] > heavy_size) {
heavy_size = size[dst];
heavy_pos = j;
}
}
if (heavy_pos != -1) {
swap(g[cur][0], g[cur][heavy_pos]);
}
}
}
void dfs_hld(int root) {
vector<pair<int, int>> st;
st.emplace_back(root, 0);
nxt[root] = root;
while (!st.empty()) {
auto [cur, state] = st.back();
st.pop_back();
if (state == 0) {
ord[id] = cur;
down[cur] = id++;
st.emplace_back(cur, 1);
for (int i = int(g[cur].size()) - 1; i >= 0; i--) {
int dst = g[cur][i];
if (dst == par[cur]) continue;
if (dst == g[cur][0]) {
nxt[dst] = nxt[cur];
} else {
nxt[dst] = dst;
}
st.emplace_back(dst, 0);
}
} else {
up[cur] = id;
}
}
}
public:
// [u, v)
vector<pair<int, int>> ascend(int u, int v) const {
vector<pair<int, int>> res;
while (nxt[u] != nxt[v]) {
res.emplace_back(down[u], down[nxt[u]]);
u = par[nxt[u]];
}
if (u != v) res.emplace_back(down[u], down[v] + 1);
return res;
}
// (u, v]
vector<pair<int, int>> descend(int u, int v) const {
if (u == v) return {};
if (nxt[u] == nxt[v]) return {{down[u] + 1, down[v]}};
auto res = descend(u, par[nxt[v]]);
res.emplace_back(down[nxt[v]], down[v]);
return res;
}
G g;
int root, id;
vector<int> size, depth, down, up, ord, nxt, par;
HLD() = default;
HLD(G& _g, int _root = 0)
: g(_g),
root(_root),
id(0),
size(g.size(), 0),
depth(g.size(), 0),
down(g.size(), -1),
up(g.size(), -1),
ord(g.size(), 0),
nxt(g.size(), root),
par(g.size(), -1) {
dfs_sz(root);
dfs_hld(root);
}
void build(int _root) {
root = _root;
id = 0;
fill(size.begin(), size.end(), 0);
fill(depth.begin(), depth.end(), 0);
fill(down.begin(), down.end(), -1);
fill(up.begin(), up.end(), -1);
fill(ord.begin(), ord.end(), 0);
fill(nxt.begin(), nxt.end(), root);
fill(par.begin(), par.end(), -1);
dfs_sz(root);
dfs_hld(root);
}
pair<int, int> idx(int i) const {
return make_pair(down[i], up[i]);
}
template <typename F>
void path_query(int u, int v, bool vertex, const F& f) {
int l = lca(u, v);
for (auto&& [a, b] : ascend(u, l)) {
int s = a + 1, t = b;
if (s > t) f(t, s);
else f(s, t);
}
if (vertex) f(down[l], down[l] + 1);
for (auto&& [a, b] : descend(l, v)) {
int s = a, t = b + 1;
if (s > t) f(t, s);
else f(s, t);
}
}
template <typename F>
void path_noncommutative_query(int u, int v, bool vertex, const F& f) {
int l = lca(u, v);
for (auto&& [a, b] : ascend(u, l)) {
f(a + 1, b);
}
if (vertex) f(down[l], down[l] + 1);
for (auto&& [a, b] : descend(l, v)) {
f(a, b + 1);
}
}
template <typename F>
void subtree_query(int u, bool vertex, const F& f) {
f(down[u] + int(!vertex), up[u]);
}
int lca(int a, int b) const {
while (nxt[a] != nxt[b]) {
if (down[a] < down[b]) swap(a, b);
a = par[nxt[a]];
}
return depth[a] < depth[b] ? a : b;
}
int dist(int a, int b) const {
return depth[a] + depth[b] - depth[lca(a, b)] * 2;
}
int kth_ancestor(int u, int k) const {
if (k < 0) return -1;
while (u >= 0) {
int h = nxt[u];
if (down[u] - k >= down[h]) {
return ord[down[u] - k];
}
k -= down[u] - down[h] + 1;
u = par[h];
}
return -1;
}
int next(int s, int t) const {
assert(s != t);
assert(0 <= s && s < int(g.size()));
assert(0 <= t && t < int(g.size()));
if (depth[s] >= depth[t]) return par[s];
int u = kth_ancestor(t, depth[t] - depth[s] - 1);
return par[u] == s ? u : par[s];
}
// s - t 間のパス上の頂点のうち s から距離 d の頂点
// dist(s, t) < d のとき -1
int jump(int s, int t, int d) const {
int lc = lca(s, t);
int d1 = depth[s] - depth[lc];
if (d <= d1) {
return kth_ancestor(s, d);
}
int d2 = d1 + depth[t] - depth[lc];
if (d <= d2) {
return kth_ancestor(t, d2 - d);
}
return -1;
}
vector<int> path(int s, int t) const {
vector<int> pre, suf;
while (depth[s] > depth[t]) {
pre.emplace_back(s);
s = par[s];
}
while (depth[s] < depth[t]) {
suf.emplace_back(t);
t = par[t];
}
while (s != t) {
pre.emplace_back(s);
suf.emplace_back(t);
s = par[s];
t = par[t];
}
pre.push_back(s);
reverse(begin(suf), end(suf));
copy(begin(suf), end(suf), back_inserter(pre));
return pre;
}
// u is in subtree of v
bool in_subtree(int u, int v) const {
return down[v] <= down[u] && down[u] < up[v];
}
};
#line 4 "library/graph/FunctionalGraph.hpp"
struct FunctionalGraph {
int N,M;
vector<int> TO;
vector<int> root;
vector<vector<int>> G;
HLD<vector<vector<int>>> hld;
FunctionalGraph() {}
FunctionalGraph(int N) : N(N), M(0), TO(N, -1), root(N, -1) {}
void add_edge(int from,int to) {
assert(0 <= from && from < N);
assert(TO[from] == -1);
++M;
TO[from] = to;
}
void build() {
assert(N == M);
unionfind uf(N);
for(int i = 0;i < N;i++) {
if(uf.same(i,TO[i])) root[i] = i;
else uf.merge(i,TO[i]);
}
for(int i = 0;i < N;i++) {
if(root[i] == i) {
root[uf.find(i)] = i;
}
}
for(int i = 0;i < N;i++) {
root[i] = root[uf.find(i)];
}
G = vector<vector<int>>(N + 1);
for(int i = 0;i < N;i++) {
if(root[i] == i) {
G[N].emplace_back(i);
}
else {
G[TO[i]].emplace_back(i);
}
}
hld = HLD<vector<vector<int>>>(G,N);
}
// from->toの距離、不可能なら-1
int dist(int from,int to) {
if(hld.down[to] <= hld.down[from] && hld.down[from] < hld.up[to]) {
return hld.depth[from] - hld.depth[to];
}
int r = root[from];
int btm = TO[r];
if(hld.down[to] <= hld.down[btm] && hld.down[btm] < hld.up[to]) {
int x = hld.depth[from] - hld.depth[r];
x++;
x += hld.depth[btm] - hld.depth[to];
return x;
}
return -1;
}
// functional graph に向かって進む
int jump(int v, long long step) {
int d = hld.depth[v];
if (step <= d - 1) return hld.jump(v, N, step);
v = root[v];
step -= d - 1;
int bottom = TO[v];
int c = hld.depth[bottom];
step %= c;
if (step == 0) return v;
return hld.jump(bottom, N, step - 1);
}
vector<int> jump_all(long long step) {
vector<int> res(N, -1);
// v の k 個先を res[w] に入れる
vector<vector<pair<int,int>>> query(N);
for(int v = 0;v < N;v++) {
int d = hld.depth[v];
int r = root[v];
if (d - 1 > step) { query[v].emplace_back(v, step); }
if (d - 1 <= step) {
long long k = step - (d - 1);
int bottom = TO[r];
int c = hld.depth[bottom];
k %= c;
if (k == 0) {
res[v] = r;
continue;
}
query[bottom].emplace_back(v, k - 1);
}
}
vector<int> path;
auto dfs = [&](auto& dfs, int v) -> void {
path.emplace_back(v);
for (auto&& [w, k]: query[v]) { res[w] = path[(int)path.size() - 1 - k]; }
for (auto&& e: G[v]) dfs(dfs, e);
path.pop_back();
};
for (auto&& e: G[N]) { dfs(dfs, e); }
return res;
}
};
#line 2 "library/math/factorize.hpp"
vector<pair<long long,int>> prime_factorization(long long n) {
vector<pair<long long,int>> ret;
int c = 0;
while(n % 2 == 0) {
c++;
n >>= 1;
}
if(c) ret.emplace_back(2,c);
for(long long i = 3; i * i <= n; i += 2) {
c = 0;
while(n % i == 0) {
n /= i;
c++;
}
if(c) ret.emplace_back(i,c);
}
if (n != 1) ret.emplace_back(n,1);
return ret;
}
vector<long long> divisor(long long n) {
vector<long long> ret;
for(long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if(i * i != n) {ret.push_back(n / i);}
}
}
sort(ret.begin(),ret.end());
return ret;
}
#line 109 "main.cpp"
void solve() {
INT(n);
LL(k);
if(k == 1) {
cout << n << '\n';
return;
}
auto div = divisor(n);
mint two;
rep(i,div.size()) two += div[i];
vm C(M);
rep(i,1,M) {
rep(j,i,M,i) {
C[j] += i;
}
}
FunctionalGraph FG(M);
rep(i,M) {
FG.add_edge(i,C[i].get());
}
FG.build();
cout << FG.jump(two.get(),k - 2) << '\n';
}
int main() {
int TT = 1;
//cin >> TT;
while(TT--) solve();
}