Overview

This problem asks you to find the smallest \(M\) that is a “perfect count” with at least \(N\) beads, and output \(M - N\). A “perfect count” turns out to be a prime number, so the problem reduces to finding the smallest prime number greater than or equal to \(N\).

Analysis

What is a “perfect count”?

\(M\) is a perfect count if, for every \(k\) with \(1 \le k \le M-1\), starting from bead \(0\) and advancing by \(k\) at a time visits all \(M\) beads.

The number of beads visited when starting from bead \(0\) and advancing by \(k\) is the smallest positive integer \(i\) such that \(ik \bmod M = 0\). This equals \(\frac{M}{\gcd(k, M)}\).

The condition for visiting all beads is \(\frac{M}{\gcd(k, M)} = M\), i.e., \(\gcd(k, M) = 1\).

Therefore, \(M\) is a perfect count if and only if:

For all \(k\) with \(1 \le k \le M-1\), \(\gcd(k, M) = 1\)

This means “all positive integers less than \(M\) are coprime to \(M\).” This holds if and only if \(M\) is prime.

Concrete example: For \(M = 5\) (prime), \(k = 1, 2, 3, 4\) are all coprime to \(5\), so it is a perfect count. On the other hand, for \(M = 6\), \(k = 2\) gives \(\gcd(2, 6) = 2 \neq 1\), so it is not a perfect count.

Why doesn’t naive primality testing work?

Since \(N\) can be as large as \(10^{12}\), trial division for primality testing (\(O(\sqrt{N})\), roughly \(10^6\) operations) is fine for a single check, but we need to perform multiple checks when searching for a prime greater than or equal to \(N\). The gap between consecutive primes is on the order of \(O(\log N)\), so trial division might be fast enough, but as a faster and more reliable method, we use the Miller-Rabin primality test.

Algorithm

1. Rephrase the problem as “find the smallest prime \(M \ge N\) and output \(M - N\).”
2. Starting from \(N\), check odd numbers in order and let \(M\) be the first prime found (if \(N \le 2\), then \(M = 2\)).
3. Use the deterministic Miller-Rabin test for primality checking. For \(n < 3.3 \times 10^{24}\), it is known that using the witnesses \(\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}\) gives exact results.

Overview of the Miller-Rabin test: Decompose \(n - 1 = 2^r \cdot d\) (where \(d\) is odd), then for each witness \(a\), compute \(a^d \bmod n\) and check conditions based on Fermat’s little theorem. If all witnesses pass, the number is determined to be prime.

Complexity

• Time complexity: Per test case, letting \(G\) be the prime gap, \(O(G \cdot w \cdot \log^2 N)\). Since \(G = O(\log N)\) and the number of witnesses \(w = 12\) is a constant, this is effectively \(O(\log^3 N)\). Overall: \(O(T \log^3 N)\).
• Space complexity: \(O(T)\) (output buffer)

Implementation Notes

• Python’s pow(a, d, n) has built-in fast modular exponentiation, making the Miller-Rabin test concise to implement.

• When \(N\) is even, searching only odd numbers starting from \(N+1\) halves the number of primality checks.

• Using sys.stdin.readline and batch output processing speeds up I/O.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.