Hello, Codeforces!

Today I'm going to talk about an unpopular technique in number theory.

## Definition and elementary properties

**Def.** Let $$$p > 2$$$ be a prime number, then we will call *quadratic residues* all $$$1 \le x \le p - 1$$$ modulo $$$p$$$ such that the equation $$$a^2 \equiv x \pmod{p}$$$ has solutions and *quadratic nonresidues* otherwise. **Note** that $$$0$$$ is neither *quadratic residue* nor *quadratic nonresidue*.

**Theorem:** quadratic residues and quadratic nonresidues are equally divided.

**Proof**

**Theorem:** Denote by $$$R$$$ a quadratic residue and by $$$N$$$ a quadratic nonresidue, then:

.

**Proof**

With these two theorems, we can already solve 103428K - Tiny Stars.

## How to check if the number is residue or nonresidue?

There are several ways to check if a number is quadratic residue. In this blog, we will look at just one of them, you can read about Gauss's lemma and law of quadratic reciprocity.

#### Euler's criterion

$$$a$$$ is a quadratic residue modulo $$$p$$$ if and only if $$$a^{{\frac{p - 1}{2}}} \equiv 1 \pmod{p}$$$, and a quadratic nonresidue if and only if $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

**Proof**

**Consequence:** $$$-1$$$ is quadratic residue if and only if $$$p = 4k + 1$$$, for some natural $$$k$$$, and quadratic nonresidue if and only if $$$p = 4k + 3$$$, for some natural $$$k$$$.

Clearly, the complexity of the number check is $$$O(\log_2p)$$$.

**Code**

## Finding $$$i$$$ modulo $$$p$$$

**Def.** $$$i$$$ is such a number that $$$i^2 = -1$$$ $$$\implies$$$ $$$i$$$ modulo $$$p$$$ let us call such a number that $$$i ^ 2 \equiv -1 \pmod{p}$$$.

**Algorithm:** If $$$p = 4k + 3$$$ for some natural $$$k$$$, then there is no such $$$i$$$. If $$$p = 2$$$, then $$$i = 1$$$. Otherwise consider the quadratic nonresidue of $$$a$$$, by Euler's criterion we know that $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$, then $$$a^{\frac{p - 1}{4}} \equiv i \pmod{p}$$$. All that remains is to find a quadratic nonresidue, for this we take a random $$$1 \le a \le p - 1$$$ and check it for $$$O(\log_2p)$$$, if it is a quadratic residue then take another random $$$a$$$. Since the number of residues and nonresidue are equal, we need $$$O(1)$$$ of such checks, so the expected running time of the algorithm is $$$O(\log_2p)$$$.

**Code**