#1179905 (C++23(gcc16)) No.3651 K-th Sum of Divisors

• 問題: No.3651 K-th Sum of Divisors
• ユーザー: yurina256
• 提出日時: 2026-08-28 21:57:13
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 5,506 bytes
• コンパイル時間: 5,466 ms
• コンパイル使用メモリ: 397,224 KB
• 実行使用メモリ: 28,672 KB
• 最終ジャッジ日時: 2026-08-28 21:57:24
• 合計ジャッジ時間: 8,680 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 10 WA * 45

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace atcoder;
using mint = modint;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n) - 1; i >= 1; i--)
#define ll long long
#define double long double
#define ull unsigned long long
#define ALL(v) (v).begin(), (v).end()
#define NP next_permutation
#define PLL pair<long long, long long>
#define VL vector<long long>
#define VVL vector<vector<long long>>
#define VVVL vector<vector<vector<long long>>>
#define VPLL vector<pair<long long, long long>>
#define STL set<long long>
#define MPLL map<long long, long long>
#define SP fixed << setprecision(12)
#define hashmap unordered_set
#define popcount __builtin_popcountll

constexpr ll inf = 4001001001001001001ll;
constexpr ll mod = /* 1000000007; //*/ 998244353;
constexpr double pi = 3.141592653589793;
constexpr double eps = 0.00000000001;
vector<ll> d8x = {1, 1, 0, -1, -1, -1, 0, 1};
vector<ll> d8y = {0, 1, 1, 1, 0, -1, -1, -1};
vector<ll> d4x = {1, 0, -1, 0};
vector<ll> d4y = {0, 1, 0, -1};
// 小数出力
// cout << setprecision(12);
// struct
typedef tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;
struct Ruiseki {
  vector<ll> v;
  Ruiseki(vector<ll>& vec) {
    ll n = vec.size();
    v.resize(n + 1);
    rep(i, n) v[i + 1] = v[i] + vec[i];
  }
  ll get(ll l, ll r) {  // 開区間になりました
    return v[r] - v[l];
  }
};
// max
template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); }
// min
template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); }
// join
template <typename T>
string join(vector<T>& vec, const string& sp = " ") {
  int si = vec.size();
  if (si == 0) {
    return "";
  } else {
    stringstream ss;
    rep(i, si - 1) {
      ss << vec[i] << sp;
    }
    ss << vec[si - 1];
    return ss.str();
  }
}
// print
template <typename T>
void pr_single(const T& x) {
  if constexpr (requires { x.val(); }) cout << x.val();
  else if constexpr (requires { typename T::value_type; } && !requires { x.substr(0); }) {
    using elem_type = typename T::value_type;
    constexpr bool is_container_of_container =
        requires { typename elem_type::value_type; } &&
        !requires(elem_type e) { e.substr(0); };
    for (int i = 0; i < (int)x.size(); i++) {
      pr_single(x[i]);
      if (i != (int)x.size() - 1) {
        if constexpr (is_container_of_container) {
          cout << "\n";
        } else {
          cout << " ";
        }
      }
    }
  } else if constexpr (requires { x.first; x.second; }) {
    pr_single(x.first);
    cout << " ";
    pr_single(x.second);
  } else if constexpr (requires { cout << x; }) {
    cout << x;
  }
}
void pr() { cout << endl; }
template <typename Head, typename... Tail>
void pr(const Head& head, const Tail&... tail) {
  pr_single(head);
  if constexpr (sizeof...(tail) > 0) {
    cout << " ";
    pr(tail...);
  } else
    cout << endl;
}
// Yes
string Yes(bool x) {
  if (x) return "Yes\n";
  return "No\n";
}
string YES(bool x) {
  if (x) return "YES\n";
  return "NO\n";
}
ll Digit(ll n) {
  ll ans = 0;
  while (n > 0) {
    n /= 10;
    ans++;
  }
  return ans;
}
bool in_range(int l, int x, int r) {  // 閉区間
  return ((l <= x) && (x <= r)) || ((r <= x) && (x <= l));
}
int div_ceil(int x, int y) {
  return (x + y - 1) / y;
}
void yakubun(ll& a, ll& b) {
  if (a < 0) {
    a = -a;
    b = -b;
  }
  if (a == 0) {
    b = 1;
    return;
  }
  if (b == 0) {
    a = 1;
    return;
  }
  ll g = gcd(abs(a), abs(b));
  a /= g;
  b /= g;
  // pr(a, b);
}
void swap(pair<ll, ll>& p) {
  auto [a, b] = p;
  p = {b, a};
}
ll _sqrt(ll x) {
  ll a = sqrt(x);
  while ((a + 1) * (a + 1) <= x) a++;
  while (a * a > x) a--;
  return a;
}
ll _pow(ll x, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
ll bs(ll l, ll r, function<bool(ll)> f) {  // l-> false, r->true
  while (r - l > 1) {
    ll mid = l + (r - l) / 2;
    if (f(mid)) r = mid;
    else
      l = mid;
  }
  return r;
}
ll op(ll a, ll b) {
  return a + b;
}
ll e() {
  return 0;
}
void solve() {
}
struct UnionFind {
  vector<int> data;  // 負ならサイズ　正なら親ノード

  UnionFind(int sz) {
    data.assign(sz, -1);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return (false);
    if (data[x] > data[y]) swap(x, y);  // Xの方が大きい状態にする
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k) {
    if (data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k) {
    return (-data[find(k)]);
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};
signed main() {
  mint::set_mod(100003);
  ll n, k;
  cin >> n >> k;
  vector<vector<mint>> dp(63, vector<mint>(100004, 0));
  rep1(i, 100004) {
    for (ll j = i; j <= 100003; j += i) {
      dp[0][j] += i;
    }
  }
  // pr(dp[0]);
  rep1(i, 63) {
    rep1(j, 100004) {
      dp[i][j] = dp[i - 1][dp[i - 1][j].val()];
    }
  }
  mint now = n;
  k--;
  rep(i, 63) {
    if ((k >> i) & 1ll) {
      now = dp[i][now.val()];
    }
  }
  pr(now);
}