概要

与えられた整数 \(N\) 以上で最小の「完全な個数」 \(M\) を見つけ、その差 \(M - N\) を求める問題です。数学的な考察により、「完全な個数」とは「素数」のことであると分かります。

考察

1. 「良い」 \(k\) の条件

ビーズの総数を \(M\)、進む歩数を \(k\) としたとき、訪れるビーズの個数は \(\frac{M}{\gcd(k, M)}\) 個になることが知られています。 これがちょうど \(M\) 個になる、すなわち \(k\) が「良い」ための条件は、\(\gcd(k, M) = 1\) であること、つまり \(k\) と \(M\) が互いに素であること です。

2. 「完全な個数」 \(M\) の正体

問題文より、\(M\) が「完全な個数」であるとは、\(1 \le k \le M-1\) を満たすすべての \(k\) が「良い」こと、すなわち \(1\) から \(M-1\) までのすべての整数が \(M\) と互いに素であること を指します。

この条件を満たす \(M\) はどのような数でしょうか？ - もし \(M\) が合成数なら、\(M\) には \(1\) より大きく \(M\) より小さい約数 \(d\) が存在します。このとき \(\gcd(d, M) = d > 1\) となり、\(k=d\) は「良い」 \(k\) ではなくなります。 - もし \(M\) が素数なら、\(1\) から \(M-1\) までのすべての整数は \(M\) の倍数ではないため、すべて \(M\) と互いに素になります。

したがって、「完全な個数」 \(M\) とは「素数」のことである と結論付けられます。

3. \(N\) 以上の最小の素数を探す

\(N\) は最大で \(10^{12}\) と非常に大きいため、エラトステネスの篩などで事前に素数を列挙することは不可能です。 しかし、素数同士の間隔（素数間隙）は \(10^{12}\) 付近でもそれほど大きくない（最大でも 500〜600 程度）ことが数学的に知られています。 そのため、\(N\) から順に \(N, N+1, N+2, \dots\) と数値を増やしながら、各数値が素数かどうかを高速に判定すれば、十分な速度で答えを見つけることができます。

アルゴリズム

1. 各テストケースについて、現在のビーズの数 \(N\) を受け取る。
2. \(m = N\) から始めて、以下の手順で最小の素数 \(M\) を探す。
   • \(m\) が素数であれば、それが求める \(M\) である。
   • \(m\) が素数でなければ、\(m\) を増やして判定を繰り返す（\(m \ge 3\) の場合は奇数のみを調べればよい）。
3. 素数判定には、大きな数に対しても高速に動作する ミラー・ラビン素数判定法 (Miller-Rabin Primality Test) を使用する。
4. 見つかった \(M\) に対して \(M - N\) を出力する。

計算量

• 時間計算量: \(1\) テストケースあたり \(O(G \times K \log^3 N)\)
  • \(G\): \(N\) から次の素数までの間隔（\(10^{12}\) 付近で数百程度）。
  • \(K\): ミラー・ラビン法で使用する基数の個数（\(10^{12}\) 程度なら 7 個程度で決定的に判定可能）。
  • 全体では \(O(T \times G \times K \log^3 N)\) となります。
• 空間計算量: \(O(1)\)
  • 判定に必要な基数などの定数メモリのみを使用します。

実装のポイント

• ミラー・ラビン素数判定法: \(10^{12}\) という巨大な数に対して is_prime を行うため、決定的な基数のセット（2, 3, 5, 7, 11, 13, 17 など）を用いることで、誤判定なく高速に素数判定を行えます。

• 探索の効率化: \(N > 2\) の場合、偶数は素数ではないため、奇数のみを判定対象にすることで探索回数を半分に減らすことができます。

• 入出力の高速化: テストケース数 \(T\) が 5000 と比較的多いため、sys.stdin.read や sys.stdout.write を用いてまとめて入出力を行うと効率的です。

  ソースコード

import sys

# Miller-Rabin primality test (deterministic for n < 3,415,500,717,283,211)
def is_prime(n):
    """
    Checks if a number n is prime using the Miller-Rabin primality test.
    The test is deterministic for n up to approximately 3.4 * 10^15.
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # Write n-1 as 2^s * d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    # Bases for deterministic Miller-Rabin up to the given range.
    # For n < 3,415,500,717,283,211, bases {2, 3, 5, 7, 11, 13, 17} are sufficient.
    for a in (2, 3, 5, 7, 11, 13, 17):
        if n <= a:
            break
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def solve():
    """
    Solves the circular necklace problem.
    A number M is a 'perfect count' if and only if M is a prime number.
    We need to find the smallest prime M >= N and output M - N.
    """
    # Read all input from stdin and split into tokens
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # The first token is the number of test cases T
    T = int(input_data[0])
    results = []
    
    # Process each test case
    for i in range(1, T + 1):
        N = int(input_data[i])
        
        # M must be a perfect count (prime) and M >= N.
        # Smallest prime >= 2 is 2.
        if N <= 2:
            results.append(0)
            continue
        
        m = N
        # If N is even and > 2, the next prime must be odd.
        if m % 2 == 0:
            m += 1
        
        # Increment m by 2 until a prime number is found.
        # The gap between primes around 10^12 is small (max gap < 600).
        while not is_prime(m):
            m += 2
        
        # Calculate the number of beads to add.
        results.append(m - N)
    
    # Join all results with newlines and print them at once for efficiency.
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。