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

• 問題: No.3651 K-th Sum of Divisors
• ユーザー: nyanpasu
• 提出日時: 2026-08-28 22:11:29
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 98 ms / 2,000 ms
• コード長: 5,269 bytes
• コンパイル時間: 6,461 ms
• コンパイル使用メモリ: 389,352 KB
• 実行使用メモリ: 53,632 KB
• 最終ジャッジ日時: 2026-08-28 22:12:41
• 合計ジャッジ時間: 13,452 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 55

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define sz(x) ((int64_t)x.size())
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in_grid(h, w, H, W) if (!(0 <= h && 0 <= w && h < H && w < W)) continue;
template<typename T> using priority_queue_g = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using vec = vector<T>;
//組み合わせ
template< typename T >
struct Combination {
    vector< T > _fact, _rfact, _inv;
    Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
        _fact[0] = _rfact[sz] = _inv[0] = 1;
        for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
        _rfact[sz] /= _fact[sz];
        for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
        for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
    }
    inline T fact(int k) const { return _fact[k]; }
    inline T rfact(int k) const { return _rfact[k]; }
    inline T inv(int k) const { return _inv[k]; }
    T P(int n, int r) const {
        if(r < 0 || n < r) return 0;
        return fact(n) * rfact(n - r);
    }
    T C(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return fact(p) * rfact(q) * rfact(p - q);
    }
    T H(int n, int r) const {
        if(n < 0 || r < 0) return (0);
        return r == 0 ? 1 : C(n + r - 1, r);
    }
};

template <typename T>
int64_t LIS (const vector<T>& V) {
    vector<T> DP(V.size());
    int len = 0;
    for (const auto& x : V) {
        auto itr = lower_bound(DP.begin(), DP.begin() + len, x);
        *itr = x;
        if (itr == DP.begin() + len) len++;
    }
    return len;
}

int64_t powmod(int64_t a, int64_t b, int64_t mod) {
    a %= mod;
    int64_t res = 1 % mod;
    while (b) {
        if (b&1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

template <typename T>
bool chtop(vector<T>& a, const T& b, int limit_size = -1) {
    if (limit_size == -1) limit_size = a.size();
    if ((int)a.size() < limit_size) {
        auto it = lower_bound(a.begin(), a.end(), b, greater<T>());
        a.insert(it, b);
        return true;
    }
    if (limit_size == 0 || b <= a.back()) return false;
    a.pop_back();
    auto it = lower_bound(a.begin(), a.end(), b, greater<T>());
    a.insert(it, b);
    return true;
}
template <typename T>
bool chbot(vector<T>& a, const T& b, int limit_size = -1) {
    if (limit_size == -1) limit_size = a.size();
    if ((int)a.size() < limit_size) {
        auto it = lower_bound(a.begin(), a.end(), b);
        a.insert(it, b);
        return true;
    }
    if (limit_size == 0 || b >= a.back()) return false;
    a.pop_back();
    auto it = lower_bound(a.begin(), a.end(), b);
    a.insert(it, b);
    return true;
}

//ループマクロ
#define     re(n)       for (int64_t r_= 0;            r_<  int64_t(n);r_++)
#define    rep(i, n)    for (int64_t i = 0;            i <  int64_t(n); i++)
#define   repp(i, n)    for (int64_t i = 0;            i <= int64_t(n); i++)
#define   rrep(i, a, b) for (int64_t i = int64_t(a);   i <  int64_t(b); i++)
#define  rrepp(i, a, b) for (int64_t i = int64_t(a);   i <= int64_t(b); i++)
#define   reep(i, n)    for (int64_t i = int64_t(n)-1; i >= 0;          i--)
#define  reepp(i, n)    for (int64_t i = int64_t(n);   i >= 0;          i--)
#define  rreep(i, a, b) for (int64_t i = int64_t(b)-1; i >= int64_t(a); i--)
#define rreepp(i, a, b) for (int64_t i = int64_t(b);   i >= int64_t(a); i--)
template<class T, class U> bool chmax(T& a, const U&b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T, class U> bool chmin(T& a, const U&b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
using lint = int64_t;
using pll = pair<int64_t, int64_t>;
using vl = vector<lint>;
using vvl = vector<vector<lint>>;
using vvvl = vector<vector<vector<lint>>>;
using vpll = vector<pair<lint,lint>>;
using ld = long double;
using mint = modint998244353;
void yn(bool b) { cout << (b ? "Yes" : "No") << endl; }
const lint MOD = 100003;
// const lint MOD = 1000000007;
const lint INF = 4004004004004004004;
const ld pi = 3.141592653589793238;
const lint dx[] = {-1,0,1,0,-1,1,1,-1};
const lint dy[] = {0,-1,0,1,-1,-1,1,1};


void solve() {
    lint n, k; cin >> n >> k;
    if (k == 1) {
        cout << n << "\n";
        return;
    }
    lint cnt = 0;
    rrepp(i,1,sqrt(n)) {
        if (n%i) continue;
        if (i*i == n) cnt += i;
        else cnt += i + n/i;
        cnt %= MOD;
    }
    k--;
    n = cnt;
    vl f(MOD+1,0);
    rrepp(i,1,MOD) {
        rrepp(j,1,sqrt(i)) {
            if (i%j) continue;
            if (j * j == i) f[i] += j;
            else f[i] += j + i/j;
            f[i] %= MOD;
        }
    }
    vvl neko(62, vl(MOD+1));
    neko[0] = f;
    rep(i,61) {
        repp(j,MOD) {
            neko[i+1][j] = neko[i][neko[i][j]];
        }
    }
    k--;
    rep(i,61) {
        if (k&1) {
            n = neko[i][n];
        }
        k /= 2;
    }
    cout << n << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}