結果

問題 No.3651 K-th Sum of Divisors
コンテスト
ユーザー 市川瑚麻
提出日時 2026-09-06 19:47:01
言語 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
結果
WA  
実行時間 -
コード長 1,665 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,781 ms
コンパイル使用メモリ 230,896 KB
実行使用メモリ 16,128 KB
最終ジャッジ日時 2026-09-06 19:47:16
合計ジャッジ時間 14,312 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 30
権限があれば一括ダウンロードができます

ソースコード

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;

    // 訪れた位置のステップ数を記録（周期検出用）
    // 2回目以降は必ず MOD(100003) 未満になる
    vector<long long> visited(MOD, -1);
    vector<long long> history;

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

    while (step <= k) {
        // 現在の値が MOD 未満のときに周期チェックを行う
        if (curr < MOD) {
            if (visited[curr] != -1) {
                // 周期を発見
                long long cycle_start = visited[curr];
                long long cycle_len = step - cycle_start;
                long long rem_steps = (k - step + 1) % 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);

        // 次の項へ（Kに達したらループを抜ける）
        if (step == k) break;
        curr = sigma[curr];
        step++;
    }

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

    return 0;
}
0