概要

\(N\) 個以上のビーズで「完全な個数」となる最小の \(M\) を求め、\(M - N\) を出力する問題です。「完全な個数」とは素数のことであり、\(N\) 以上の最小の素数を見つける問題に帰着されます。

考察

「完全な個数」とは何か？

\(M\) が完全な個数であるとは、\(1 \le k \le M-1\) のすべての \(k\) について、ビーズ \(0\) から \(k\) ずつ進んだとき \(M\) 個すべてのビーズを訪れることです。

ビーズ \(0\) から \(k\) ずつ進んで訪れるビーズの個数は、\(ik \bmod M = 0\) となる最小の正整数 \(i\) です。これは \(\frac{M}{\gcd(k, M)}\) に等しいです。

すべてのビーズを訪れる条件は \(\frac{M}{\gcd(k, M)} = M\)、すなわち \(\gcd(k, M) = 1\) です。

したがって、\(M\) が完全な個数であるとは：

\(1 \le k \le M-1\) のすべての \(k\) について \(\gcd(k, M) = 1\)

これは「\(M\) 未満のすべての正整数が \(M\) と互いに素」であることを意味します。これが成り立つのは \(M\) が素数のとき、かつそのときに限り ます。

具体例: \(M = 5\)（素数）の場合、\(k = 1, 2, 3, 4\) はすべて \(5\) と互いに素なので完全な個数です。一方 \(M = 6\) の場合、\(k = 2\) は \(\gcd(2, 6) = 2 \neq 1\) なので完全な個数ではありません。

なぜ素朴な素数判定ではダメか？

\(N\) は最大 \(10^{12}\) と非常に大きいため、試し割りによる素数判定（\(O(\sqrt{N})\) で約 \(10^6\) 回）でも 1 回あたりは問題ありませんが、\(N\) 以上の素数を探す際に複数回判定を繰り返す必要があります。素数間のギャップは \(O(\log N)\) 程度なので、試し割りでも間に合う可能性はありますが、より高速で確実な方法として ミラー・ラビン素数判定法 を用います。

アルゴリズム

1. 問題を「\(N\) 以上の最小の素数 \(M\) を求め、\(M - N\) を出力する」と言い換える。
2. \(N\) から始めて奇数を順に調べ、最初に見つかった素数を \(M\) とする（\(N \le 2\) の場合は \(M = 2\)）。
3. 素数判定には 決定的ミラー・ラビン法 を使う。\(n < 3.3 \times 10^{24}\) の範囲では、witness として \(\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}\) を使えば正確に判定できることが知られている。

ミラー・ラビン法の概要: \(n - 1 = 2^r \cdot d\)（\(d\) は奇数）と分解し、各 witness \(a\) について \(a^d \bmod n\) を計算し、フェルマーの小定理に基づく条件をチェックします。すべての witness をパスすれば素数と判定します。

計算量

• 時間計算量: 1 テストケースあたり、素数間ギャップを \(G\) とすると \(O(G \cdot w \cdot \log^2 N)\)。\(G = O(\log N)\)、witness 数 \(w = 12\) は定数なので、実質 \(O(\log^3 N)\) 程度。全体では \(O(T \log^3 N)\)。
• 空間計算量: \(O(T)\)（出力バッファ）

実装のポイント

• Python の pow(a, d, n) は高速なモジュラ冪乗を内蔵しているため、ミラー・ラビン法を簡潔に書ける。

• \(N\) が偶数の場合、\(N+1\) から奇数のみを探索することで判定回数を半減できる。

• sys.stdin.readline と出力の一括処理で I/O を高速化している。

  ソースコード

import sys
input = sys.stdin.readline

def is_prime(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    # Small primes check
    for p in [5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n == p:
            return True
        if n % p == 0:
            return False
    # Miller-Rabin
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1
    witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in witnesses:
        if a >= n:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def next_prime(n):
    if n <= 2:
        return 2
    if n % 2 == 0:
        n += 1
    while not is_prime(n):
        n += 2
    return n

T = int(input())
out = []
for _ in range(T):
    N = int(input())
    M = next_prime(N)
    out.append(str(M - N))
print('\n'.join(out))

---

この解説は claude4.6opus-thinking によって生成されました。