Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### EJIC_B_KEDAX's blog

By EJIC_B_KEDAX, history, 3 weeks ago, translation,

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.

Proof

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

$R \cdot R = R$
$N \cdot R = N$
$N \cdot N = R$

.

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
• +87

By EJIC_B_KEDAX, 4 weeks ago,

Hello, Codeforces!

I am pleased to invite you to participate in Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2), which will be held at Jul/18/2024 17:35 (Moscow time). You will be given 8 problems and 2 hours to solve them. It will be rated for all participants.

The theme of the round is computer games!

Tasks for the round were prepared by EJIC_B_KEDAX, zwezdinv, green_gold_dog, molney, azureglow and Sokol080808.

We would like to thank everyone who assisted in the preparation of this round:

1. Our coordinator 74TrAkToR for his useful advices and help in preparing the tasks!

2. Qwerty1232 for red interest in testing the round.

3. turmax for the red-black testing.

4. makrav, arbuzick, Anonymous_Noob, Hyperbolic for red testing.

5. Mr_Ell, krigare, marzipan, TimVen74, coder8080, MichsSS, PieArmy, tvladm, Vladosiya, bashem for purple testing.

6. Algolagon, PoDuReMaN, zarubin, IgorA, leoper, kovir_aleksey_korroy, Kosya, Vamperox for blue testing.

7. MakGeoKar, viteli for cyan testing.

8. Sonya_2009, ishaandas1 for green testing.

9. MikeMirzayanov for the excellent Codeforces and Polygon systems.

I also congratulate green_gold_dog on his birthday and wish him good luck on IOI.

This round is supported by NEAR!

NEAR was founded in 2017 by Illia Polosukhin, one of the creators of Transformers, and Alex Skidanov as an attempt to build an artificial system capable of solving competitive programming problems. You can read more about that attempt here.

Ultimately, NEAR pivoted into building a blockchain protocol, which it launched in 2020.

This year, NEAR started NEAR.AI, a new lab with a mission to build AI systems that are open and available to everyone, instead of being controlled by a few mega-corporations.

One of the areas of focus is making models capable of reasoning reliably, and for that, competitive programming problems provide a great environment. To help us build it, we invite all members of the Codeforces community with a rating of Specialist or higher (1400+) to help us annotate step-by-step explanations of solutions to competitive programming problems. We want to annotate a very large set of problems of all difficulty levels, and pay relatively high rewards in NEAR per annotation. You can join the system following this: https://mirror.codeforces.com/settings/near-connect-account

Thanks to NEAR for providing the following prizes to the contestants:

• 1st place: 512 Ⓝ;
• 2nd and 3rd places: 256 Ⓝ each;
• 4th to 7th places: 128 Ⓝ each;
• and so on;
• 512th to 1023th places: 1 Ⓝ each.

Score distribution: $500-1000-1250-2000-2000-2500-2750-3750$

Good luck!

UPD: Editorial

UPD2: Congratulations for the winners:

• -222

By EJIC_B_KEDAX, history, 14 months ago, translation,

Hello, Codeforces!

You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them)

• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by: zwezdinv, EJIC_B_KEDAX, molney, Sokol080808, meowcneil, Vladosiya.

We would like to thank:

1. Vladosiya for coordinating the round.

2. MikeMirzayanov for Polygon and Codeforces platforms and testing.

3. tute7627 for red-black testing.

4. ace5, sevlll777, oursaco, lightseba, gmusya, pavlekn, vrintle, tolbi for yellow testing.

5. diskoteka, moonpie24, SashaT9, shell_wataru, MGod, Phantom_Performer, tarattata1, alex.kudryashov, Restricted, sdyakonov for purple testing.

6. Alex239, MrEssiorx, olyazyryanova, marzipan, Pa_sha, Rudro25, azureglow, IHateGeometry, ivan.alexeev, krigare for blue testing.

7. Guevara74, ctraxxd for cyan testing.

8. sahal, exhausted, viteli, prohamer80 for green testing.

Good luck!

UPD: Editorial.

• +377