概要

未点検のサーバー集合を管理しながら、規則通りに巡回をシミュレーションします。
重要なのは「現在の番号 \(k\) と共通の素因数を持つ未点検の番号のうち最小のもの」を高速に見つけることです。

考察

現在いるサーバー番号を \(k\) とします。

\(k \geq 2\) のとき、次に移動できる番号 \(m\) は

\[ \gcd(k, m) \geq 2 \]

を満たす必要があります。

これは言い換えると、

\(m\) が \(k\) の素因数のうち少なくとも 1 つで割り切れる

ということです。

例えば \(k = 12\) なら、素因数は \(2, 3\) なので、次に行ける番号は「\(2\) の倍数」または「\(3\) の倍数」です。

したがって、次に移動する番号は

\(k\) の各素因数 \(p\) について、\(k\) より大きい未点検の \(p\) の倍数の最小値を求め、その中の最小値

になります。

---

素朴に、毎回 \(k+1, k+2, \dots, N\) を順に見て \(\gcd(k,m)\) を計算すると、最悪で \(O(N^2 \log N)\) 程度かかってしまい、\(N \leq 5 \times 10^5\) では間に合いません。

そこで、

• 全体の未点検番号から最小のものを取る
• ある素数 \(p\) について、未点検の \(p\) の倍数のうち、指定位置以降で最小のものを取る

という操作を高速に行えるようにします。

このために、Union-Find を「削除済み要素を飛ばして次の未削除要素を探すデータ構造」として使います。

アルゴリズム

1. 最小素因数を前計算する

まず、各整数 \(x\) について最小の素因数 spf[x] を求めます。

これにより、任意の \(x\) の素因数を高速に列挙できます。

例えば、

\[ 12 = 2^2 \times 3 \]

なら、素因数として \(2, 3\) を取り出します。

---

2. 全体の未点検集合を管理する

巡回開始時には、

未点検のサーバーのうち番号が最小のもの

を選ぶ必要があります。

そのために、\(1,2,\dots,N\) 全体について「まだ残っている最小の番号」を探せる Union-Find を用意します。

削除済みの番号 \(x\) は、次の番号 \(x+1\) に飛ばすようにします。

つまり、

global_parent[x] = find_root(global_parent, x + 1);

とすることで、以後 \(x\) は探索時にスキップされます。

find_root(global_parent, 1) を呼ぶと、現在未点検の最小番号が得られます。

---

3. 各素数ごとに「未点検の倍数」を管理する

次に、各素数 \(p\) について、

\[ p, 2p, 3p, \dots \]

という \(p\) の倍数列を考えます。

例えば \(p=3, N=15\) なら、

\[ 3, 6, 9, 12, 15 \]

です。

この列に対しても Union-Find を使い、削除済みの倍数を飛ばせるようにします。

番号 \(x\) を点検したら、\(x\) の各素因数 \(p\) について、\(x\) を「\(p\) の倍数列」から削除します。

例えば \(x=12\) なら、素因数は \(2,3\) なので、

• \(2\) の倍数列から \(12\) を削除
• \(3\) の倍数列から \(12\) を削除

します。

---

4. 次に移動する番号を求める

現在の番号を \(k\) とします。

\(k=1\) の場合

\(1\) は素因数を持たないので、問題文通り特別扱いします。

未点検の番号のうち \(1\) より大きい最小のものを探せばよいです。

find_root(global_parent, 2)

で求められます。

\(k \geq 2\) の場合

\(k\) の素因数を列挙します。

各素因数 \(p\) について、

未点検の \(p\) の倍数のうち、\(k\) より大きい最小のもの

を求めます。

その候補たちの最小値が、次に移動する番号です。

例えば \(k=12\) の場合、素因数は \(2,3\) です。

• 未点検の \(2\) の倍数で \(12\) より大きい最小値
• 未点検の \(3\) の倍数で \(12\) より大きい最小値

を調べ、その小さい方を採用します。

これにより、問題文の条件

\[ \gcd(k,m) \geq 2 \]

を満たす最小の \(m\) を正しく求められます。

---

5. 実際のシミュレーション

全体の流れは以下です。

1. 未点検の最小番号 \(s\) を取る
2. 存在しなければ終了
3. 巡回回数を \(1\) 増やす
4. \(s\) を点検済みにする
5. 現在地から次に移動できる番号を探す
6. 見つかれば点検済みにして移動
7. 見つからなければその巡回を終了し、1 に戻る

各番号は一度だけ点検済みになるため、全体として効率よく処理できます。

計算量

• 時間計算量: \(O(N \log \log N)\) 程度
• 空間計算量: \(O(N \log \log N)\) 程度

各整数について、その異なる素因数を処理します。
\(1\) から \(N\) までの異なる素因数の個数の合計は \(O(N \log \log N)\) 程度です。

また、各素数 \(p\) について \(p\) の倍数列を管理するため、必要な要素数の合計は

\[ \sum_{p \leq N} \left\lfloor \frac{N}{p} \right\rfloor \]

であり、これも \(O(N \log \log N)\) 程度です。

実装のポイント

Union-Find で「次の未削除要素」を探す

通常の Union-Find とは少し使い方が異なります。

削除された要素 \(x\) について、

parent[x] = find_root(parent, x + 1);

とします。

すると、find_root(parent, x) は「\(x\) 以上でまだ削除されていない最小の要素」を返すようになります。

---

素因数は重複を除いて処理する

例えば \(12 = 2^2 \times 3\) ですが、処理する素因数は \(2,3\) のみです。

コードでは、

while (t % p == 0) t /= p;

によって、同じ素因数をまとめて飛ばしています。

---

各素数の倍数列は 1 本の配列に詰める

概念的には、各素数 \(p\) ごとに別々の Union-Find 配列を持ちます。

ただし実装では、それらをまとめて 1 本の配列 mult_parent に詰めています。

offset[p] は、素数 \(p\) の倍数列が mult_parent のどこから始まるかを表します。

例えば、\(p\) の倍数 \(x\) は、\(x = jp\) と書けるので、倍数列内では \(j-1\) 番目に対応します。

そのため、コードでは

idx = offset[p] + x / p - 1;

として位置を求めています。

ソースコード

#include <bits/stdc++.h>
using namespace std;

static inline int find_root(vector<int>& parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

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

    int N;
    cin >> N;

    vector<int> spf(N + 1, 0), primes;
    for (int i = 2; i <= N; i++) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || 1LL * i * p > N) break;
            spf[i * p] = p;
        }
    }

    vector<int> offset(N + 1, -1);
    long long total = 0;
    for (int p : primes) {
        offset[p] = (int)total;
        total += N / p + 1;
    }

    vector<int> mult_parent((size_t)total);
    iota(mult_parent.begin(), mult_parent.end(), 0);

    vector<int> global_parent(N + 2);
    iota(global_parent.begin(), global_parent.end(), 0);

    auto erase_number = [&](int x) {
        global_parent[x] = find_root(global_parent, x + 1);

        int t = x;
        while (t > 1) {
            int p = spf[t];
            int idx = offset[p] + x / p - 1;
            mult_parent[idx] = find_root(mult_parent, idx + 1);
            while (t % p == 0) t /= p;
        }
    };

    auto get_next = [&](int k) {
        int res = N + 1;

        if (k == 1) {
            int v = find_root(global_parent, 2);
            return v <= N ? v : N + 1;
        }

        int t = k;
        while (t > 1) {
            int p = spf[t];
            int off = offset[p];
            int m = N / p;
            int idx = off + k / p;

            int r = find_root(mult_parent, idx);
            if (r < off + m) {
                int cand = (r - off + 1) * p;
                if (cand < res) res = cand;
            }

            while (t % p == 0) t /= p;
        }

        return res;
    };

    int answer = 0;

    while (true) {
        int s = find_root(global_parent, 1);
        if (s > N) break;

        answer++;
        int cur = s;
        erase_number(cur);

        while (true) {
            int nxt = get_next(cur);
            if (nxt > N) break;
            cur = nxt;
            erase_number(cur);
        }
    }

    cout << answer << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。