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

• 問題: No.3651 K-th Sum of Divisors
• ユーザー: yuki4869.
• 提出日時: 2026-08-29 00:40:17
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 43 ms / 2,000 ms
• コード長: 11,880 bytes
• コンパイル時間: 4,751 ms
• コンパイル使用メモリ: 391,900 KB
• 実行使用メモリ: 36,352 KB
• 最終ジャッジ日時: 2026-08-29 00:40:43
• 合計ジャッジ時間: 9,288 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std; using namespace atcoder;
using ll=long long; using LL=__int128; using mint=modint998244353;
using pll=pair<ll,ll>; using tu=tuple<ll,ll,ll>; using vl=vector<ll>; using vb=vector<bool>; using vvb=vector<vb>; using vvl=vector<vl>; using vs=vector<string>; using vld=vector<long double>; using vc=vector<char>; using vmi=vector<mint>;
using Graph=vector<vector<pair<ll,ll>>>; using graph=vector<vector<ll>>;
template<class T> using rpq=priority_queue<T,vector<T>,greater<T>>; // 小さい順priority_queue
using inverse_priority_queue=rpq<ll>;
const ll Inf=2147483647LL, Inf9=1000000000LL, inf=9223372036854775807LL, inf18=1000000000000000000LL, mod=998244353LL;
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)
#define rep3(i,s,t) for(ll i=(ll)(s);i<(ll)(t);i++)
#define pb push_back
#define p(s) cout<<(s)<<'\n'
#define p2(s,t) cout<<(s)<<" "<<(t)<<'\n'
#define p3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<'\n'
#define p4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<'\n'
#define pe(s) cout<<(s)<<' '
#define pval(s) cout<<(s).val()<<'\n'
#define Sort(A) sort(all(A))
#define RSort(A) sort(rall(A))
#define p_yes() p("Yes")
#define p_no() p("No")

template<class T> inline ll sz(const T& x){return (ll)x.size();} // サイズ取得
ostream& operator<<(ostream& os,const mint& x){return os<<x.val();} // mint出力
istream& operator>>(istream& is,mint& x){ll v; is>>v; x=mint(v); return is;} // mint入力
template<class T> inline bool chmin(T& a,const T& b){if(a>b){a=b; return true;} return false;} // 最小値更新
template<class T> inline bool chmax(T& a,const T& b){if(a<b){a=b; return true;} return false;} // 最大値更新
template<class T,class U> ll LB(const vector<T>& v,const U& a){return lower_bound(all(v),a)-v.begin();} // lower_boundのindex
template<class T,class U> ll UB(const vector<T>& v,const U& a){return upper_bound(all(v),a)-v.begin();} // upper_boundのindex
template<class T> T vec_min(const vector<T>& v){assert(!v.empty()); return *min_element(all(v));} // vectorの最小値
template<class T> T vec_max(const vector<T>& v){assert(!v.empty()); return *max_element(all(v));} // vectorの最大値
template<class T> T vec_sum(const vector<T>& v){T res=T(0); for(const auto& x:v) res+=x; return res;} // vectorの総和

template<class T=ll> vector<T> cin_vl(ll n){vector<T> ret(n); rep(i,n) cin>>ret[i]; return ret;} // vector入力、型省略時ll
template<class T=ll> vector<vector<T>> cin_vvl(ll h,ll w){vector<vector<T>> ret(h,vector<T>(w)); rep(i,h) rep(j,w) cin>>ret[i][j]; return ret;} // h*w入力、型省略時ll
template<class T=ll> pair<vector<T>,vector<T>> cin_xy(ll n){vector<T> x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; return {x,y};} // x,y入力、型省略時ll
template<class T=ll> tuple<vector<T>,vector<T>,vector<T>> cin_xyz(ll n){vector<T> x(n),y(n),z(n); rep(i,n) cin>>x[i]>>y[i]>>z[i]; return {x,y,z};} // x,y,z入力、型省略時ll
template<class T=ll> vector<vector<T>> Cin_vl(ll n,ll k){vector<vector<T>> ret(k,vector<T>(n)); rep(i,n) rep(j,k) cin>>ret[j][i]; return ret;} // n行k列入力を列ごと保持、型省略時ll
template<class T=ll> vector<pair<T,T>> cin_pairs(ll n){vector<pair<T,T>> ret(n); rep(i,n) cin>>ret[i].first>>ret[i].second; return ret;} // pair列入力、型省略時ll
template<class T=ll> vector<tuple<T,T,T>> cin_tuples(ll n){vector<tuple<T,T,T>> ret(n); rep(i,n){T a,b,c; cin>>a>>b>>c; ret[i]={a,b,c};} return ret;} // 3要素tuple列入力、型省略時ll

template<class T> void cout_vl(const vector<T>& a,char sep=' ',char end='\n'){rep(i,sz(a)){if(i) cout<<sep; cout<<a[i];} cout<<end;} // vector出力
template<class T> void Cout_vl(const vector<T>& a,const vector<T>& b){rep(i,sz(a)) cout<<a[i]<<" "<<b[i]<<'\n';} // 2vector縦出力
template<class T> void cout_vvl(const vector<vector<T>>& a){for(const auto& e:a) cout_vl(e);} // 2次元vector出力

ll ceil_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return (a+b-1)/b; return -((-a)/b);} // 切り上げ除算
ll floor_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return a/b; return -((-a+b-1)/b);} // 切り下げ除算
ll isqrt(ll n){ll x=sqrtl(n); while((LL)(x+1)*(x+1)<=n) x++; while((LL)x*x>n) x--; return x;} // floor(sqrt(n))
template<class T> vector<T> sort_unique_vec(vector<T> v){sort(all(v)); v.erase(unique(all(v)),v.end()); return v;} // sortして重複削除した新vector
template<class T> vector<ll> compress(const vector<T>& v){auto xs=sort_unique_vec(v); vector<ll> ret; for(auto& x:v) ret.pb(LB(xs,x)); return ret;} // 座標圧縮後のindex列
template<class T> vector<T> prefix_sum(const vector<T>& v){vector<T> s(sz(v)+1,0); rep(i,sz(v)) s[i+1]=s[i]+v[i]; return s;} // 1次元累積和
template<class T> T range_sum(const vector<T>& s,ll l,ll r){return s[r]-s[l];} // 累積和から[l,r)の和
template<class T> vector<pair<T,ll>> run_length(const vector<T>& v){vector<pair<T,ll>> ret; for(auto& x:v){if(ret.empty()||ret.back().first!=x) ret.pb({x,1}); else ret.back().second++;} return ret;} // ランレングス圧縮
vector<pair<char,ll>> run_length(const string& s){vector<pair<char,ll>> ret; for(char c:s){if(ret.empty()||ret.back().first!=c) ret.pb({c,1}); else ret.back().second++;} return ret;} // 文字列ランレングス圧縮
template<class T> ll argmin(const vector<T>& v){assert(!v.empty()); return min_element(all(v))-v.begin();} // 最小値のindex
template<class T> ll argmax(const vector<T>& v){assert(!v.empty()); return max_element(all(v))-v.begin();} // 最大値のindex
template<class T> bool in_vec(const vector<T>& v,const T& x){return binary_search(all(v),x);} // sort済vectorに存在するか

ll gcd(ll a,ll b){if(b==0) return abs(a); return gcd(b,a%b);} // 最大公約数
ll lcm(ll a,ll b){return a/gcd(a,b)*b;} // 最小公倍数
ll Exp(ll x,ll y){ll cnt=-1; while(x>0) x/=y,cnt++; return cnt;} // y進桁数-1
ll powmod(ll x,ll k,ll m){if(k==0) return 1%m; ll r=powmod(x,k/2,m); r=(LL)r*r%m; if(k&1) r=(LL)r*x%m; return r;} // mod累乗
template<class T> T square(T x){return x*x;} // 二乗
template<class T> void Uni_erase(vector<T>& v){sort(all(v)); v.erase(unique(all(v)),v.end());} // sortして重複削除
inline bool OutIn(ll x,ll y,ll h,ll w){return 0<=x&&x<h&&0<=y&&y<w;} // グリッド範囲内判定
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Random(ll l,ll r){uniform_int_distribution<ll> dist(l,r-1); return dist(rng);} // [l,r)乱数
void YesNo(bool x){x?p_yes():p_no();} // Yes/No出力
vl vl_n(ll n){vl ret(n); rep(i,n) ret[i]=i; return ret;} // 0..n-1のvector生成

vl dx={0,1,0,-1}, dy={1,0,-1,0};
vl dx8={1,1,0,-1,-1,-1,0,1}, dy8={0,1,1,1,0,-1,-1,-1}; // 8近傍

vector<mint> fac,finv;
void factorial(ll N=1000000LL){ll M=N+100; fac.assign(M+1,1); finv.assign(M+1,1); rep1(i,M) fac[i]=fac[i-1]*i; finv[M]=fac[M].inv(); for(ll i=M;i>=1;i--) finv[i-1]=finv[i]*i;} // N+100まで階乗・逆階乗前計算
void ensure_factorial(ll N){if((ll)fac.size()>N) return; factorial(N);} // 階乗表の不足分確保
mint nCr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[r]*finv[N-r];} // 二項係数
mint nPr(ll N,ll r){if(N<0||r<0||N<r) return 0; ensure_factorial(N); return fac[N]*finv[N-r];} // 順列数

//FunctionalGraph

struct FunctionalGraph {
    static constexpr int LOG=64;
    int n;
    vector<int> to,depth,cid,pos,entry;
    vector<vector<int>> up,cycle;

    FunctionalGraph(const vector<int>& to):n(to.size()),to(to){ build(); }

    void build(){
        vector<vector<int>> rev(n);
        vector<int> deg(n);
        for(int v=0;v<n;v++) rev[to[v]].push_back(v),deg[to[v]]++;

        queue<int> q;
        for(int v=0;v<n;v++) if(!deg[v]) q.push(v);
        while(!q.empty()){
            int v=q.front(); q.pop();
            if(!--deg[to[v]]) q.push(to[v]);
        }

        cid.assign(n,-1); pos.assign(n,-1);
        for(int s=0;s<n;s++) if(deg[s]&&cid[s]==-1){
            int id=cycle.size(),v=s;
            cycle.push_back({});
            do{
                cid[v]=id;
                pos[v]=cycle[id].size();
                cycle[id].push_back(v);
                v=to[v];
            }while(v!=s);
        }

        depth.assign(n,-1); entry.assign(n,-1);
        for(int v=0;v<n;v++) if(cid[v]!=-1)
            depth[v]=0,entry[v]=v,q.push(v);

        while(!q.empty()){
            int v=q.front(); q.pop();
            for(int u:rev[v]) if(depth[u]==-1){
                cid[u]=cid[v];
                depth[u]=depth[v]+1;
                entry[u]=entry[v];
                q.push(u);
            }
        }

        up.assign(LOG,vector<int>(n));
        up[0]=to;
        for(int k=1;k<LOG;k++)
            for(int v=0;v<n;v++)
                up[k][v]=up[k-1][up[k-1][v]];
    }

    int jump(int v,unsigned long long k) const {
        for(int i=0;i<LOG;i++) if(k>>i&1) v=up[i][v];
        return v;
    }

    bool in_cycle(int v) const { return depth[v]==0; }
    int cycle_id(int v) const { return cid[v]; }
    int cycle_size(int v) const { return cycle[cid[v]].size(); }
    int dist_to_cycle(int v) const { return depth[v]; }
    int cycle_entry(int v) const { return entry[v]; }

    long long distance(int a,int b) const {
        if(cid[a]!=cid[b]) return -1;

        if(depth[b]){
            if(depth[a]<depth[b]) return -1;
            long long d=depth[a]-depth[b];
            return jump(a,d)==b?d:-1;
        }

        long long d=depth[a];
        int v=jump(a,d),len=cycle[cid[a]].size();
        return d+(pos[b]-pos[v]+len)%len;
    }

    bool reachable(int a,int b) const { return distance(a,b)!=-1; }
};

/*
Functional Graph
0-indexed
各頂点から出る辺がちょうど1本

vector<int> to(n);                             // v -> to[v]
FunctionalGraph fg(to);                        // 構築 O(N log 2^64)

fg.jump(v,k);                                  // vからk回進んだ頂点 O(log k)

fg.in_cycle(v);                                // vがサイクル上ならtrue
fg.cycle_id(v);                                // 最終的に入るサイクル番号
fg.cycle_size(v);                              // 最終的に入るサイクルの長さ
fg.dist_to_cycle(v);                           // サイクルまでの距離
fg.cycle_entry(v);                             // 最初に到達するサイクル頂点

fg.distance(a,b);                              // aからbへの最小移動回数
                                                // 到達不能なら-1
fg.reachable(a,b);                             // aからbへ到達可能か

fg.cycle[id];                                  // id番目のサイクル頂点列
                                                // toの向き順

例:
vector<int> to={1,2,3,4,5,2,1};
FunctionalGraph fg(to);

fg.jump(0,3);                                  // 3
fg.dist_to_cycle(0);                           // 2
fg.cycle_entry(0);                             // 2
fg.in_cycle(2);                                // true
fg.cycle_size(0);                              // 4
fg.distance(0,4);                              // 4
fg.reachable(6,3);                             // true
*/
signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    

    ll n, k;
    cin >> n >> k;

    if(k == 1){
        p(n);
        return 0;
    }
    vl v(100003);
    ll cnt = 0;
    rep1(i,max(n,100003LL)){
        rep1(j,100003){
            if(i*j >= 100003) break;
            else v[i*j] += i;
        }

        if(n%i == 0) cnt += i;

    }

    vector<int> to(100003);

    rep(i,100003) to[i] = v[i]%100003;

    ll x = cnt%100003;

    FunctionalGraph fg(to);

    p(fg.jump(x,k-2));
}