結果

問題 No.3651 K-th Sum of Divisors
コンテスト
ユーザー 市川瑚麻
提出日時 2026-09-06 19:48:52
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 132 ms / 2,000 ms
+ 882µs
コード長 1,331 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,366 ms
コンパイル使用メモリ 231,764 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2026-09-06 19:49:11
合計ジャッジ時間 13,884 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <print>

using namespace std;

const int MOD = 100003;
const int MAX = 3000005;

vector<int> sigma(MAX, 0);

void precompute() {
    for (int i = 1; i < MAX; ++i) {
        for (int j = i; j < MAX; j += i) {
            sigma[j] = (sigma[j] + i) % MOD;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    precompute();

    long long n, k;
    if (!(cin >> n >> k)) return 0;

    vector<long long> visited(MOD, -1);
    vector<long long> history;

    long long curr = n;
    long long step = 1;

    while (step <= k) {
        if (curr < MOD) {
            if (visited[curr] != -1) {
                long long cycle_start = visited[curr];
                long long cycle_len = step - cycle_start;
                
                // 正しい遷移数 (k - step) を使って余りを計算
                long long rem_steps = (k - step) % cycle_len;
                long long ans_idx = cycle_start - 1 + rem_steps;
                
                std::println("{}", history[ans_idx]);
                return 0;
            }
            visited[curr] = step;
        }

        history.push_back(curr);

        if (step == k) break;
        curr = sigma[curr];
        step++;
    }

    std::println("{}", curr);

    return 0;
}
0