結果
| 問題 | No.3651 K-th Sum of Divisors |
| コンテスト | |
| ユーザー |
 ウソチー
|
| 提出日時 | 2026-08-28 23:21:52 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 182 ms / 2,000 ms |
| + 686µs | |
| コード長 | 25,319 bytes |
| 記録 | |
| コンパイル時間 | 4,994 ms |
| コンパイル使用メモリ | 383,492 KB |
| 実行使用メモリ | 16,896 KB |
| 最終ジャッジ日時 | 2026-08-28 23:22:11 |
| 合計ジャッジ時間 | 18,444 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 55 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#include <iostream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
struct FastIO {
FastIO() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
}
};
inline FastIO fast_io_init;
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);
template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
return is >> p.first >> p.second;
}
template <typename Tuple, std::size_t... I>
void read_tuple_impl(std::istream& is, Tuple& t, std::index_sequence<I...>) {
(..., (is >> std::get<I>(t)));
}
template <typename... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& t) {
read_tuple_impl(is, t, std::index_sequence_for<Args...>{});
return is;
}
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (auto& elem : v) {
is >> elem;
}
return is;
}
using default_type = long;
template <typename... Args>
void read(Args&... args) {
(std::cin >> ... >> args);
}
template <typename T = default_type>
T read_val() {
T val;
std::cin >> val;
return val;
}
template <typename T1 = default_type, typename T2 = default_type>
std::pair<T1, T2> read_pair() {
std::pair<T1, T2> p;
std::cin >> p;
return p;
}
template <typename... Args>
std::tuple<Args...> read_tuple() {
std::tuple<Args...> t;
std::cin >> t;
return t;
}
template <typename T = default_type>
std::vector<T> read_vec(int n) {
std::vector<T> v(n);
std::cin >> v;
return v;
}
template <typename T = default_type>
std::vector<T> read_vec() {
int n;
std::cin >> n;
return read_vec<T>(n);
}
template <typename T1 = default_type, typename T2 = default_type>
std::vector<std::pair<T1, T2>> read_vec_pair(int n) {
std::vector<std::pair<T1, T2>> v(n);
std::cin >> v;
return v;
}
template <typename T1 = default_type, typename T2 = default_type>
std::vector<std::pair<T1, T2>> read_vec_pair() {
int n;
std::cin >> n;
return read_vec_pair<T1, T2>(n);
}
template <typename... Args>
std::vector<std::tuple<Args...>> read_vec_tuple(int n) {
std::vector<std::tuple<Args...>> v(n);
std::cin >> v;
return v;
}
template <typename... Args>
std::vector<std::tuple<Args...>> read_vec_tuple() {
int n;
std::cin >> n;
return read_vec_tuple<Args...>(n);
}
template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid(int h, int w) {
std::vector<std::vector<T>> grid(h, std::vector<T>(w));
std::cin >> grid;
return grid;
}
template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid() {
int h, w;
std::cin >> h >> w;
return read_vec_grid<T>(h, w);
}
template <typename T = default_type>
std::vector<std::vector<T>> read_vec_var(int n) {
std::vector<std::vector<T>> res(n);
for (int i = 0; i < n; ++i) {
int m;
std::cin >> m;
res[i] = read_vec<T>(m);
}
return res;
}
template <typename T = default_type>
std::vector<std::vector<T>> read_vec_var() {
int n;
std::cin >> n;
return read_vec_var<T>(n);
}
template <typename T = default_type>
T read_zero_idx() {
T val;
std::cin >> val;
return val - 1;
}
inline std::vector<std::vector<int>> read_graph(int n, int m, bool directed = false) {
std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; ++i) {
int u = read_zero_idx<int>();
int v = read_zero_idx<int>();
g[u].push_back(v);
if (!directed) {
g[v].push_back(u);
}
}
return g;
}
inline std::vector<std::vector<int>> read_graph(bool directed = false) {
int n, m;
std::cin >> n >> m;
return read_graph(n, m, directed);
}
#include <istream>
#include <numeric>
#include <print>
#include <vector>
#define ALL(a) (a).begin(), (a).end()
using i128 = __int128;
template <typename T, typename U>
inline bool chmin(T& a, const U& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T, typename U>
inline bool chmax(T& a, const U& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <std::integral T>
inline T div_ceil(T a, T b) {
if (a > 0) return a / b + (a % b != 0);
return a / b;
}
template <std::integral T>
inline T div_floor(T a, T b) {
if (a < 0) return a / b - (a % b != 0);
return a / b;
}
template <std::integral T>
inline T mod(T a, T m) {
a %= m;
if (a < 0) a += m;
return a;
}
template <typename T>
inline constexpr T INF = std::numeric_limits<T>::max() / 2;
template <>
inline constexpr float INF<float> = std::numeric_limits<float>::infinity();
template <>
inline constexpr double INF<double> = std::numeric_limits<double>::infinity();
template <>
inline constexpr long double INF<long double> = std::numeric_limits<long double>::infinity();
template <typename T = int>
inline std::vector<T> iota_vec(int n, T start = 0) {
std::vector<T> v(n);
std::iota(v.begin(), v.end(), start);
return v;
}
template <typename T>
inline std::vector<T> doubled_vec(const std::vector<T>& v) {
std::vector<T> res;
res.reserve(v.size() * 2);
res.insert(res.end(), v.begin(), v.end());
res.insert(res.end(), v.begin(), v.end());
return res;
}
inline void Yes(bool b = true) {
std::println("{}", (b ? "Yes" : "No"));
}
inline void No() {
std::println("No");
}
#ifdef LOCAL
#include <utility/debug.hpp>
#else
#define debug(...)
#endif
#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>
struct FunctionalGraph {
int n;
int log_k;
std::vector<int> to;
std::vector<int> cycle_id;
std::vector<int> cycle_pos;
std::vector<std::vector<int>> cycles;
std::vector<int> root;
std::vector<int> depth;
std::vector<std::vector<int>> doubling;
std::vector<std::vector<int>> children;
bool is_built = false;
std::vector<long long> tree_pref;
std::vector<std::vector<long long>> cycle_pref;
std::vector<long long> cycle_sum;
bool has_weight = false;
explicit FunctionalGraph(int n, const std::vector<int>& to)
: n(n), to(to), cycle_id(n, -1), cycle_pos(n, -1), root(n, -1), depth(n, 0) {
log_k = std::max(1, std::bit_width(static_cast<unsigned int>(n)));
}
void build() {
std::vector<int> state(n, 0);
std::vector<int> path;
for (int i = 0; i < n; i++) {
if (state[i] != 0) continue;
int curr = i;
path.clear();
while (state[curr] == 0) {
state[curr] = 1;
path.push_back(curr);
curr = to[curr];
}
if (state[curr] == 1) {
std::vector<int> cycle;
bool in_cycle = false;
for (int v : path) {
if (v == curr) in_cycle = true;
if (in_cycle) {
cycle_id[v] = cycles.size();
cycle_pos[v] = cycle.size();
root[v] = v;
depth[v] = 0;
cycle.push_back(v);
}
}
cycles.push_back(cycle);
}
for (int j = static_cast<int>(path.size()) - 1; j >= 0; j--) {
int u = path[j];
state[u] = 2;
if (root[u] == -1) {
int next_v = to[u];
root[u] = root[next_v];
depth[u] = depth[next_v] + 1;
}
}
}
children.assign(n, {});
for (int i = 0; i < n; i++) {
if (cycle_id[i] == -1) {
children[to[i]].push_back(i);
}
}
doubling.assign(log_k, std::vector<int>(n));
for (int i = 0; i < n; i++) doubling[0][i] = to[i];
for (int k = 0; k < log_k - 1; k++) {
for (int i = 0; i < n; i++) {
doubling[k + 1][i] = doubling[k][doubling[k][i]];
}
}
is_built = true;
}
template <typename T>
void build_weight(const std::vector<T>& weight) {
assert(is_built && "You must call build() before calling build_weight().");
assert(static_cast<int>(weight.size()) == n);
tree_pref.assign(n, 0);
int num_cycles = cycles.size();
cycle_pref.assign(num_cycles, {});
cycle_sum.assign(num_cycles, 0);
for (int cid = 0; cid < num_cycles; cid++) {
for (int r : cycles[cid]) {
tree_pref[r] = 0;
std::vector<int> q = {r};
int head = 0;
while (head < static_cast<int>(q.size())) {
int p = q[head++];
for (int c : children[p]) {
tree_pref[c] = tree_pref[p] + static_cast<long long>(weight[c]);
q.push_back(c);
}
}
}
}
for (int cid = 0; cid < num_cycles; cid++) {
int sz = cycles[cid].size();
cycle_pref[cid].assign(sz + 1, 0);
for (int i = 0; i < sz; i++) {
int v = cycles[cid][i];
cycle_pref[cid][i + 1] = cycle_pref[cid][i] + static_cast<long long>(weight[v]);
cycle_sum[cid] += static_cast<long long>(weight[v]);
}
}
has_weight = true;
}
int jump(int u, long long k) const {
assert(is_built && "You must call build() before using jump().");
if (k <= depth[u]) {
for (int i = 0; k > 0; i++, k >>= 1) {
if (k & 1) u = doubling[i][u];
}
return u;
}
k -= depth[u];
int r = root[u];
int cid = cycle_id[r];
int c_size = cycles[cid].size();
return cycles[cid][(cycle_pos[r] + k) % c_size];
}
long long path_sum(int u, long long k) const {
assert(has_weight && "build_weight must be called before evaluating path_sum");
if (k <= 0) return 0;
long long ans = 0;
if (k <= depth[u]) {
int v = jump(u, k);
ans = tree_pref[u] - tree_pref[v];
} else {
ans += tree_pref[u];
k -= depth[u];
int r = root[u];
int cid = cycle_id[r];
long long sz = cycles[cid].size();
long long loops = k / sz;
ans += loops * cycle_sum[cid];
int rem = k % sz;
if (rem > 0) {
int start_idx = cycle_pos[r];
if (start_idx + rem <= sz) {
ans += cycle_pref[cid][start_idx + rem] - cycle_pref[cid][start_idx];
} else {
ans += cycle_pref[cid][sz] - cycle_pref[cid][start_idx];
ans += cycle_pref[cid][(start_idx + rem) % sz];
}
}
}
return ans;
}
long long dist(int u, int v) const {
assert(is_built && "You must call build() before using dist().");
if (root[u] != root[v]) {
if (cycle_id[root[u]] != cycle_id[root[v]]) return -1;
if (cycle_id[v] == -1) return -1;
}
if (cycle_id[v] == -1) {
if (depth[u] < depth[v]) return -1;
int diff = depth[u] - depth[v];
if (jump(u, diff) == v) return diff;
return -1;
} else {
long long d = depth[u];
int r_u = root[u];
int c_size = get_cycle_size(r_u);
int diff_cycle = (cycle_pos[v] - cycle_pos[r_u] + c_size) % c_size;
return d + diff_cycle;
}
}
int get_cycle_size(int u) const {
assert(is_built && "You must call build() before using get_cycle_size().");
return cycles[cycle_id[root[u]]].size();
}
bool on_cycle(int u) const {
assert(is_built && "You must call build() before using on_cycle().");
return cycle_id[u] != -1;
}
int dist_to_cycle(int u) const {
assert(is_built && "You must call build() before using dist_to_cycle().");
return depth[u];
}
};
#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <limits>
#include <numeric>
#include <random>
#include <vector>
namespace prime {
namespace internal {
inline long long mod_mul(long long a, long long b, long long mod) { return (__int128)a * b % mod; }
inline long long mod_pow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = mod_mul(result, base, mod);
base = mod_mul(base, base, mod);
exp >>= 1;
}
return result;
}
inline long long ceil_div(long long x, long long y) {
long long q = x / y;
long long r = x % y;
if (r > 0) ++q;
return q;
}
inline long long isqrt_floor(long long x) {
if (x <= 0) return 0;
long long r = static_cast<long long>(std::sqrt(static_cast<long double>(x)));
while ((r + 1) <= x / (r + 1)) ++r;
while (r > x / r) --r;
return r;
}
}
inline bool is_prime_mr(long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
int r = 0;
while (d % 2 == 0) {
d /= 2;
r++;
}
static constexpr std::array<long long, 7> witnesses = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
for (long long a : witnesses) {
long long a_mod = a % n;
if (a_mod == 0) continue;
long long x = internal::mod_pow(a_mod, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int i = 0; i < r - 1; i++) {
x = (__int128)x * x % n;
if (x == n - 1) {
composite = false;
break;
}
}
if (composite) return false;
}
return true;
}
inline std::vector<std::pair<long long, long long>> factorize(long long n) {
std::vector<std::pair<long long, long long>> result;
if (n <= 1) return result;
for (long long p = 2; p <= n / p; p++) {
if (n % p == 0) {
long long cnt = 0;
while (n % p == 0) {
n /= p;
cnt++;
}
result.emplace_back(p, cnt);
}
}
if (n > 1) result.emplace_back(n, 1);
return result;
}
namespace internal {
inline long long pollard_rho(long long n) {
if (n % 2 == 0) return 2;
if (is_prime_mr(n)) return n;
static std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
while (true) {
long long c = rng() % (n - 1) + 1;
auto f = [&](long long x) { return (mod_mul(x, x, n) + c) % n; };
long long x = rng() % (n - 2) + 2;
long long y = x;
long long g = 1;
while (g == 1) {
long long ys = y;
long long q = 1;
constexpr int batch = 128;
for (int r = 1; g == 1; r <<= 1) {
x = y;
for (int i = 0; i < r; i++) y = f(y);
for (int k = 0; g == 1 && k < r; k += batch) {
ys = y;
int bound = std::min(batch, r - k);
for (int i = 0; i < bound; i++) {
y = f(y);
q = mod_mul(q, std::abs(x - y), n);
}
g = std::gcd(q, n);
}
}
if (g == n) {
g = 1;
while (g == 1) {
ys = f(ys);
g = std::gcd(std::abs(x - ys), n);
}
}
}
if (g != n) return g;
}
}
inline void collect_factors(long long n, std::vector<long long>& result) {
if (n <= 1) return;
if (is_prime_mr(n)) {
result.push_back(n);
return;
}
long long d = pollard_rho(n);
collect_factors(d, result);
collect_factors(n / d, result);
}
}
inline std::vector<std::pair<long long, long long>> factorize_fast(long long n) {
std::vector<long long> primes;
internal::collect_factors(n, primes);
std::sort(primes.begin(), primes.end());
std::vector<std::pair<long long, long long>> result;
for (long long p : primes) {
if (!result.empty() && result.back().first == p) {
result.back().second++;
} else {
result.emplace_back(p, 1);
}
}
return result;
}
inline std::vector<long long> divisors(long long n) {
if (n <= 0) return {};
std::vector<long long> result = {1};
for (auto [p, e] : factorize_fast(n)) {
int sz = static_cast<int>(result.size());
long long pw = 1;
for (long long i = 0; i < e; i++) {
pw *= p;
for (int j = 0; j < sz; j++) {
result.push_back(result[j] * pw);
}
}
}
std::sort(result.begin(), result.end());
return result;
}
struct Eratosthenes {
std::vector<bool> is_prime_table;
std::vector<long long> prime_list;
std::vector<int> min_factor;
explicit Eratosthenes(int n) {
if (n < 0) n = 0;
is_prime_table.assign(n + 1, true);
min_factor.assign(n + 1, 0);
is_prime_table[0] = false;
if (n >= 1) {
is_prime_table[1] = false;
min_factor[1] = 1;
}
for (int i = 2; i <= n; i++) {
if (is_prime_table[i]) {
prime_list.push_back(i);
min_factor[i] = i;
for (long long j = (long long)i * i; j <= n; j += i) {
is_prime_table[j] = false;
if (min_factor[j] == 0) min_factor[j] = i;
}
}
}
}
bool is_prime(int n) const {
return 0 <= n && n < static_cast<int>(is_prime_table.size()) && is_prime_table[n];
}
const std::vector<long long>& primes() const { return prime_list; }
std::vector<std::pair<long long, long long>> factorize(int n) const {
if (n <= 1 || n >= static_cast<int>(min_factor.size())) return {};
std::vector<std::pair<long long, long long>> result;
while (n > 1) {
int p = min_factor[n];
long long cnt = 0;
while (min_factor[n] == p) {
n /= p;
cnt++;
}
result.emplace_back(p, cnt);
}
return result;
}
std::vector<long long> divisors(int n) const {
if (n <= 0 || n >= static_cast<int>(min_factor.size())) return {};
std::vector<long long> result = {1};
for (auto [p, e] : factorize(n)) {
int sz = static_cast<int>(result.size());
long long pw = 1;
for (long long i = 0; i < e; i++) {
pw *= p;
for (int j = 0; j < sz; j++) {
result.push_back(result[j] * pw);
}
}
}
return result;
}
};
struct LinearSieve {
std::vector<long long> primes;
std::vector<int> min_factor;
std::vector<int> phi;
std::vector<int> mobius;
explicit LinearSieve(int n) {
if (n < 0) n = 0;
min_factor.assign(n + 1, 0);
phi.assign(n + 1, 0);
mobius.assign(n + 1, 0);
if (n >= 1) {
phi[1] = 1;
mobius[1] = 1;
}
for (int i = 2; i <= n; i++) {
if (min_factor[i] == 0) {
primes.push_back(i);
min_factor[i] = i;
phi[i] = i - 1;
mobius[i] = -1;
}
for (long long p : primes) {
if (p * i > n) break;
int pi = static_cast<int>(p * i);
min_factor[pi] = static_cast<int>(p);
if (i % p == 0) {
phi[pi] = phi[i] * static_cast<int>(p);
mobius[pi] = 0;
break;
} else {
phi[pi] = phi[i] * (static_cast<int>(p) - 1);
mobius[pi] = -mobius[i];
}
}
}
}
bool is_prime(int n) const {
return n >= 2 && n < static_cast<int>(min_factor.size()) && min_factor[n] == n;
}
std::vector<std::pair<long long, long long>> factorize(int n) const {
if (n <= 1 || n >= static_cast<int>(min_factor.size())) return {};
std::vector<std::pair<long long, long long>> result;
while (n > 1) {
int p = min_factor[n];
long long cnt = 0;
while (n % p == 0) {
n /= p;
cnt++;
}
result.emplace_back(p, cnt);
}
return result;
}
};
inline std::vector<long long> segment_sieve(long long L, long long R) {
if (L < 2) L = 2;
if (R < L) return {};
long long sqrtR = internal::isqrt_floor(R);
assert(sqrtR <= std::numeric_limits<int>::max() &&
"segment_sieve: sqrt(R) must fit in int for Eratosthenes.");
if (sqrtR > std::numeric_limits<int>::max()) return {};
Eratosthenes sieve(static_cast<int>(sqrtR));
const auto& small_primes = sieve.primes();
std::vector<bool> is_prime(R - L + 1, true);
for (long long p : small_primes) {
long long start = std::max(1LL * p * p, internal::ceil_div(L, p) * 1LL * p);
for (long long j = start; j <= R; j += p) {
is_prime[j - L] = false;
}
}
std::vector<long long> result;
for (long long i = L; i <= R; i++) {
if (is_prime[i - L]) result.push_back(i);
}
return result;
}
inline std::vector<bool> segment_sieve_bool(long long L, long long R) {
if (R < L) return {};
std::vector<bool> result(R - L + 1, true);
if (L < 2) {
long long last = std::min(R, 1LL);
if (last >= L) {
std::fill(result.begin(), result.begin() + (last - L + 1), false);
}
}
if (R < 2) return result;
long long sqrtR = internal::isqrt_floor(R);
assert(sqrtR <= std::numeric_limits<int>::max() &&
"segment_sieve_bool: sqrt(R) must fit in int for Eratosthenes.");
if (sqrtR > std::numeric_limits<int>::max()) return {};
Eratosthenes sieve(static_cast<int>(sqrtR));
const auto& small_primes = sieve.primes();
for (long long p : small_primes) {
long long start = std::max(1LL * p * p, internal::ceil_div(L, p) * 1LL * p);
for (long long j = start; j <= R; j += p) {
result[j - L] = false;
}
}
return result;
}
inline long long count_primes_range(long long L, long long R) {
auto primes = segment_sieve(L, R);
return primes.size();
}
inline std::vector<long long> distinct_prime_factor_count_table(int n) {
if (n < 0) return {};
std::vector<long long> count(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (count[i] == 0) {
for (int j = i; j <= n; j += i) {
count[j]++;
}
}
}
return count;
}
inline std::vector<long long> total_prime_factor_count_table(int n) {
if (n < 0) return {};
std::vector<long long> count(n + 1, 0);
std::vector<int> min_factor(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (min_factor[i] == 0) {
for (int j = i; j <= n; j += i) {
if (min_factor[j] == 0) min_factor[j] = i;
}
}
count[i] = count[i / min_factor[i]] + 1;
}
return count;
}
inline std::vector<long long> prime_count_table(int n) {
if (n < 0) return {};
std::vector<bool> is_prime(n + 1, true);
std::vector<long long> cnt(n + 1, 0);
if (n >= 0) is_prime[0] = false;
if (n >= 1) is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
for (int j = i * 2; j <= n; j += i) is_prime[j] = false;
}
cnt[i] = cnt[i - 1] + is_prime[i];
}
return cnt;
}
inline long long euler_phi(long long n) {
if (n <= 0) return 0;
long long result = n;
for (long long p = 2; p <= n / p; p++) {
if (n % p == 0) {
while (n % p == 0) n /= p;
result -= result / p;
}
}
if (n > 1) result -= result / n;
return result;
}
}
void solve() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long N, K;
read(N, K);
const int MOD = 100003;
vector<int> to(MOD + 1, 0);
for (int i = 1; i <= MOD; i++) {
auto vec = prime::divisors(i);
long tmp = 0;
for (auto p : vec) {
tmp += p;
tmp %= MOD;
}
to[i] = tmp;
}
auto vec = prime::divisors(N);
long tmp = 0;
for (auto p : vec) {
tmp += p;
tmp %= MOD;
}
int cur = tmp;
if (K == 1) {
println("{}", N);
} else {
FunctionalGraph fg(MOD + 1, to);
fg.build();
auto ans = fg.jump(cur, K - 2);
println("{}", ans);
}
}
int main() {
solve();
}