I created a virtual contest, but I made a mistake in setting the time. This competition is in the gym. I now want to cancel this virtual participation and create a new one. But I didn't find the cancellation interface. Thanks in advice.

Congruence

The congruence equation is one of the fundamental concepts in number theory:

Let $$$m$$$ be a given positive integer, and let $$$a$$$ and $$$b$$$ be integers. If $$$m\mid(a−b)$$$, then $$$a$$$ is congruent to $$$b$$$ modulo $$$m$$$, denoted as $$$a\equiv b\pmod m$$$ or $$$a\equiv b(m)$$$.

Other forms of expressing congruence include:

• $$$a=b+km$$$
• $$$a$$$ and $$$b$$$ have the same remainder when divided by $$$m$$$

Properties of congruence equations:

• If $$$a_1\equiv b_1\pmod m$$$ and $$$a_2\equiv b_2 \pmod m$$$, then $$$a_1 + b_1 \equiv a_2 + b_2 \pmod m$$$
• If $$$a\equiv b \pmod m$$$, then $$$a\equiv b + km\pmod m$$$, where $$$k$$$ is an integer
• If $$$a_1\equiv b_1 \pmod m$$$ and $$$a_2\equiv b_2 \pmod m$$$, then $$$a_1 b_1\equiv a_2 b_2 \pmod m$$$

Finding the smallest positive integer solution for the congruence equation $$$ax \equiv 1 \pmod b$$$ involves transforming the equation into $$$ax+by=1$$$ and using the Extended Euclidean Algorithm (EXGCD) to solve it.

EXGCD

The fundamental equation is to find $$$ax+by=1$$$, for instance, $$$ 8x+3y=1 $$$.

A step-by-step breakdown is performed to arrive at a solution:

• If $$$a < b$$$ in the equation $$$ax + by = 1$$$, no modifications are needed.
• When $$$a$$$ and $$$b$$$ are not coprime in the equation $$$ax + by = 1$$$, adjustments are necessary.
• For an equation in the form $$$ax + by = c$$$, the algorithm needs to be adjusted by dividing $$$a$$$, $$$b$$$, and $$$c$$$ by their greatest common divisor ($$$\gcd$$$) to yield a coprime equation. The final result using EXGCD yields $$$x=\frac{c}{\gcd(a,b)}$$$ and $$$y=0$$$.
• To find specific solutions or multiple solutions, adjustments are made to ensure $$$x$$$ is a positive minimum. Techniques like % operations or loops are employed to handle these cases.

Multiplicative Inverse (Modular Inverse)

Addition and multiplication operations are modular-friendly, but division isn't. Multiplicative inverse, denoted as $$$b^{-1}$$$ with respect to modulo $$$p$$$ (where $$$p$$$ is a prime number), satisfies the equation $$$(b\times b^{-1}) \pmod p = 1$$$. The range of $$$b^{-1}$$$ is $$$[0,p-1]$$$.

• Fermat's Little Theorem states that if $$$p$$$ is a prime number and integer $$$a$$$ is not a multiple of $$$p$$$, then $$$a^{p-1}\pmod p=1$$$.
• For a prime $$$p$$$, the modular inverse of $$$a$$$ is $$$a^{p-2}$$$, often computed using fast exponentiation techniques.
• If $$$p$$$ is not prime, the EXGCD method is employed to solve $$$b\times b^{-1} \equiv 1 \pmod p$$$, provided $$$b$$$ and $$$p$$$ are coprime. If they aren't, the inverse doesn't exist.
• Linear preprocessing from $$$1$$$ to $$$p-1$$$ can be utilized to compute inverses efficiently by using $$$a=p \text{ mod } i$$$ and $$$b=\frac{p}{i}$$$.

NOI Gold Coach Wang_Xiaoguang taught me last weekend.

The $$$\text{Miller Rabin}$$$ algorithm is a randomization algorithm used to test whether an integer is a prime. It is based on Fermat's small theorem and quadratic detection theorem, and determines whether an integer may be a prime number through multiple random tests. The basic idea of the algorithm is to perform a series of randomness proofs, and if an integer passes these tests, it is likely to be a prime number. If an integer fails any of these tests, then it is definitely not a prime number.

The following are the basic steps of the $$$\text {Miller Rabin} $$$ algorithm: 1. Select the integer $$$n$$$ to be tested: First, select an integer $$$n$$$ greater than $$$1$$$ to determine if it is a prime number.

1. Decomposing $$$n-1$$$ into $$$2^t\times u$$$: Calculate the prime factorization of $$$n-1$$$, where $$$u$$$ is an odd number and $$$t$$$ is a non negative integer, representing the number of factors $$$2$$$.

2. Select Random Evidence Number $$$a$$$: Randomly select an integer $$$a$$$ from the interval $$$[2,n-2]$$$.

3. Calculate $$$v=a^u \mod n$$$: Calculate the modulus of $$$n$$$ to the power of $$$u$$$ of $$$a$$$, and obtain $$$v$$$.

4. Check if $$$v$$$ is equal to $$$1$$$:

• If $$$v=1$$$, then continue with the next round of testing and choose a new random evidence number of $$$a$$$.

• If $$$v$$$ is not equal to $$$1$$$, go to the next step.

1. Repeat square detection $t $times:

• Perform the $$$t$$$ sub square operation on $$$v(v=v ^ 2\mod n)$$$ while checking if $$$v$$$ is equal to $$$n-1$$$.

• If $$$v=n-1$$$, continue with the next round of testing and select a new random evidence number of $$$a$$$.

• If $$$v$$$ is not equal to $$$n-1$$$, continue the square operation and check up to a maximum of $$$t-1$$$ times.

1. Check the final result:

• If $$$v$$$ is still not equal to $$$n-1$$$ after $$$t$$$ squared detection, then $$$n$$$ is considered not a prime number and can be determined to be a composite number.

• If $$$v$$$ equals $$$n-1$$$ after $$$t$$$ tests, then $$$n$$$ may be a prime number and continue with the next round of testing.

1. Repeat multiple tests: Repeat the above steps and select different random evidence numbers $$$a$$$ for testing. Usually, repeated testing multiple times can improve the accuracy of the algorithm.

Summary: The reliability of the $$$\text{Miller Rabin}$$$ algorithm depends on the selection of iteration times and random evidence numbers. Usually, conducting multiple tests (such as $$$15$$$ or more) and selecting a random number of evidence can make the algorithm highly reliable in practice, but it is still a random algorithm. Therefore, although it can quickly exclude most composite numbers, it cannot provide absolute proof.

Code:

import random
def millerRabin(n):
    if n<3 or n%2==0:
        return n==2
    u,t=n-1,0
    while u%2==0:
        u=u//2
        t=t+1
    test_time=8
    for i in range(test_time):
        a=random.randint(2,n-1)
        v=pow(a,u,n)
        if v==1:
            continue
        s=0
        while s<t:
            if v==n-1:
                break
            v=v*v%n
            s=s+1
        if s==t:
            return False
    return True
t=int(input())
for i in range(t):
    x=int(input())
    y=millerRabin(x)
    if y==True:
        print("YES")
    if y==False:
        print("NO")