Overview

Given an integer \(N\), find the smallest “perfect count” \(M\) that is at least \(N\), and compute the difference \(M - N\). Through mathematical reasoning, we can determine that a “perfect count” is in fact a “prime number”.

Analysis

1. Condition for a “good” \(k\)

When the total number of beads is \(M\) and the step size is \(k\), it is known that the number of beads visited is \(\frac{M}{\gcd(k, M)}\). For this to be exactly \(M\), i.e., for \(k\) to be “good”, the condition is \(\gcd(k, M) = 1\), meaning \(k\) and \(M\) must be coprime.

2. The true identity of a “perfect count” \(M\)

According to the problem statement, \(M\) is a “perfect count” if and only if every \(k\) satisfying \(1 \le k \le M-1\) is “good”, meaning every integer from \(1\) to \(M-1\) is coprime with \(M\).

What kind of number \(M\) satisfies this condition? - If \(M\) is composite, then \(M\) has a divisor \(d\) with \(1 < d < M\). In this case, \(\gcd(d, M) = d > 1\), so \(k = d\) is not a “good” \(k\). - If \(M\) is prime, then every integer from \(1\) to \(M-1\) is not a multiple of \(M\), so they are all coprime with \(M\).

Therefore, we conclude that a “perfect count” \(M\) is a “prime number”.

3. Finding the smallest prime greater than or equal to \(N\)

Since \(N\) can be as large as \(10^{12}\), it is impossible to enumerate primes in advance using methods like the Sieve of Eratosthenes. However, it is mathematically known that the gaps between consecutive primes (prime gaps) near \(10^{12}\) are not very large (at most around 500–600). Therefore, by incrementing from \(N\) as \(N, N+1, N+2, \dots\) and quickly testing each number for primality, we can find the answer fast enough.

Algorithm

1. For each test case, read the current number of beads \(N\).
2. Starting from \(m = N\), search for the smallest prime \(M\) as follows:
   • If \(m\) is prime, then it is the desired \(M\).
   • If \(m\) is not prime, increment \(m\) and repeat the test (for \(m \ge 3\), it suffices to check only odd numbers).
3. For primality testing, use the Miller-Rabin Primality Test, which works efficiently even for very large numbers.
4. Output \(M - N\) for the found \(M\).

Complexity

• Time complexity: \(O(G \times K \log^3 N)\) per test case
  • \(G\): The gap from \(N\) to the next prime (on the order of a few hundred near \(10^{12}\)).
  • \(K\): The number of bases used in the Miller-Rabin test (around 7 bases suffice for deterministic testing up to \(10^{12}\)).
  • Overall: \(O(T \times G \times K \log^3 N)\).
• Space complexity: \(O(1)\)
  • Only constant memory is used for the bases and other constants needed for the test.

Implementation Notes

• Miller-Rabin Primality Test: Since we need to perform is_prime on numbers as large as \(10^{12}\), using a deterministic set of bases (such as 2, 3, 5, 7, 11, 13, 17) allows us to perform primality testing quickly without any false results.

• Search optimization: When \(N > 2\), even numbers are not prime, so by only testing odd numbers, we can halve the number of checks.

• Fast I/O: Since the number of test cases \(T\) can be as large as 5000, it is efficient to use batch I/O with sys.stdin.read or sys.stdout.write.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.