概要

各巡回では、現在の番号 \(k\) より大きく、かつ \(k\) と共通の素因数を持つ未点検サーバーのうち最小のものへ移動します。
この操作を高速にシミュレーションし、巡回を開始した回数を数えます。

考察

巡回中に移動できる先は常に「現在の番号より大きい番号」です。
したがって、各巡回で訪れる番号列は単調増加し、各サーバーは一度だけ点検されます。

素朴な方法の問題点

現在地を \(k\) として、次に行くサーバーを探すために毎回

• \(k+1, k+2, \dots, N\) を順に調べる
• それぞれについて \(\gcd(k, m) \geq 2\) か判定する

という方法を取ると、最悪で \(O(N^2)\) になってしまい、\(N \leq 5 \times 10^5\) では間に合いません。

重要な観察

\(k \geq 2\) のとき、ある番号 \(m\) が \(k\) と共通の素因数を持つことは、

\(m\) が \(k\) の素因数のどれかで割り切れる

ことと同じです。

例えば \(k = 6\) の素因数は \(2, 3\) です。
このとき次の候補は、

• \(2\) の倍数で未点検のもの
• \(3\) の倍数で未点検のもの

のうち、\(k\) より大きい最小の番号です。

したがって、\(k\) の素因数 \(p\) それぞれについて

\(k\) より大きい未点検の \(p\) の倍数の最小値

を求め、その最小値を取ればよいです。

未点検の最小値を高速に求める

「削除済みの要素を飛ばして、次に残っている要素を求める」ために、Union-Find のような「次ポインタ」を使います。

配列 parent を用意し、ある番号 \(x\) を点検済みにしたら、

\[ parent[x] = find(x+1) \]

とします。
すると find(x) は「\(x\) 以上でまだ点検されていない最小の番号」を返せます。

これを次の 2 種類用意します。

1. 全体用

   • 「未点検の番号全体」から最小を探す
   • 巡回開始時や、\(k=1\) の特別処理に使う

2. 素数 \(p\) ごとの倍数用

   • \(p\) の倍数だけを対象に、未点検の最小の倍数を探す
   • 実際には倍数 \(p \times q\) を添字 \(q\) で管理する

アルゴリズム

まず、各整数 \(x\) について、その素因数の一覧 factors[x] を前計算します。

ただし、素数 \(p > \frac{N}{2}\) は無視して構いません。
なぜなら、\(p > \frac{N}{2}\) の倍数は \(N\) 以下には \(p\) 自身しか存在せず、\(p\) より大きい倍数へ移動することができないからです。

前計算

1. \(H = \lfloor N/2 \rfloor\) とする
2. エラトステネスの篩で \(H\) 以下の素数を列挙する
3. 各素数 \(p\) について、
   • \(p, 2p, 3p, \dots\) に \(p\) を素因数として追加する
   • \(p\) の倍数管理用の Union-Find 配列を用意する

点検処理

サーバー \(x\) を点検したら、

• 全体用 Union-Find から \(x\) を削除する
• \(x\) の各素因数 \(p\) について、\(p\) の倍数管理用 Union-Find から \(x\) を削除する

具体的に、\(x = p \times q\) なら、素数 \(p\) 用の管理配列では添字 \(q\) を削除します。

巡回のシミュレーション

未点検サーバーが残っている間、以下を繰り返します。

1. 全体用 Union-Find で最小の未点検番号 \(s\) を求める
2. 新しい巡回を始めるので答えを \(1\) 増やす
3. 現在地を \(k=s\) とし、\(k\) を点検済みにする
4. 次のサーバーを探す
   • \(k=1\) の場合
     全体用 Union-Find で \(2\) 以上の未点検最小番号を求める
   • \(k \geq 2\) の場合
     \(k\) の各素因数 \(p\) について、\(k\) より大きい未点検の \(p\) の倍数を求める
     その最小値を次のサーバーとする
5. 次が存在しなければ、この巡回を終了する
6. 存在すればそこへ移動して、同様に続ける

例えば \(k=6\) のとき、素因数は \(2,3\) です。
未点検の \(2\) の倍数の最小候補が \(8\)、未点検の \(3\) の倍数の最小候補が \(9\) なら、次に移動するのは \(8\) です。

計算量

• 時間計算量: \(O(N \log \log N \cdot \alpha(N))\)
• 空間計算量: \(O(N \log \log N)\)

ここで \(\alpha(N)\) は Union-Find の逆アッカーマン関数で、実用上はほぼ定数です。

各数 \(x\) について見る素因数の個数の総和は

\[ \sum_{p \leq N/2} \left\lfloor \frac{N}{p} \right\rfloor = O(N \log \log N) \]

なので、全体として高速に処理できます。

実装のポイント

• 全体用 Union-Find は「未点検の最小番号」を求めるために使います。

• 素数 \(p\) ごとの Union-Find は、添字 \(q\) が番号 \(p \times q\) に対応します。

• \(p\) の倍数で \(k\) より大きいものを探すときは、\(q = \frac{k}{p} + 1\) から find します。

• 番号 \(N+1\) や、各素数用配列の末尾に番兵を置くことで、「次が存在しない」場合を扱いやすくしています。

• 素因数は重複して持つ必要はありません。例えば \(12 = 2^2 \times 3\) ですが、必要なのは \(2,3\) だけです。

  ソースコード

import sys
from math import isqrt

def main():
    N = int(sys.stdin.buffer.readline())
    H = N // 2

    factors = [[] for _ in range(N + 1)]
    parents = [None] * (H + 1)

    if H >= 2:
        is_prime = bytearray(b'\x01') * (H + 1)
        is_prime[0] = 0
        is_prime[1] = 0

        for i in range(2, isqrt(H) + 1):
            if is_prime[i]:
                start = i * i
                is_prime[start:H + 1:i] = b'\x00' * (((H - start) // i) + 1)

        for p in range(2, H + 1):
            if is_prime[p]:
                parents[p] = list(range(N // p + 2))
                for j in range(p, N + 1, p):
                    factors[j].append(p)

    gpar = list(range(N + 2))
    INF = N + 1

    def gfind(x):
        while gpar[x] != x:
            gpar[x] = gpar[gpar[x]]
            x = gpar[x]
        return x

    def visit(x):
        y = x + 1
        while gpar[y] != y:
            gpar[y] = gpar[gpar[y]]
            y = gpar[y]
        gpar[x] = y

        fs = factors[x]
        for p in fs:
            par = parents[p]
            idx = x // p
            y = idx + 1
            while par[y] != y:
                par[y] = par[par[y]]
                y = par[y]
            par[idx] = y
        return fs

    ans = 0

    while True:
        s = gfind(1)
        if s > N:
            break

        ans += 1
        k = s
        fs = visit(k)

        while True:
            if k == 1:
                nxt = gfind(2)
            else:
                nxt = INF
                for p in fs:
                    par = parents[p]
                    idx = k // p + 1
                    y = idx
                    while par[y] != y:
                        par[y] = par[par[y]]
                        y = par[y]
                    cand = p * y
                    if cand < nxt:
                        nxt = cand

            if nxt > N:
                break

            k = nxt
            fs = visit(k)

    print(ans)

if __name__ == "__main__":
    main()

---

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