Определение и элементарные свойства
Опр. Пусть $$$p > 2$$$ простое число, тогда квадратичным вычетом по модулю $$$p$$$ назовём все $$$1 \le x \le p - 1$$$, такие, что уравнение $$$a^2 \equiv x \pmod{p}$$$ имеет решения и квадратичным невычетом иначе. Обратите внимание, что $$$0$$$ не является ни квадратичным вычетом, ни квадратичным невычетом.
Теорема: Квадратичных вычетов и крадратичных невычетов поровну.
Теорема: Обозначим за $$$B$$$ квадратичный вычет, а за $$$H$$$ квадратичный невычет, тогда:
С помощью этих двух теорем уже можно решить 103428K - Tiny Stars.
Как проверить, число вычет или невычет?
Есть несколько способов проветь является ли число квадратичным вычетом. В этом блоге мы рассмотрим только один из них, вы можете почитать про лемму Гаусса и квадратичный закон взаимности.
Критерий Эйлера
$$$a$$$ является квадратичным вычетом по модулю $$$p$$$ тогда и только тогда, когда $$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$$, и квадратичным невычетом тогда и только тогда, когда $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.
Следствие: $$$-1$$$ является квадратичным вычетом тогда и только тогда, когда $$$p = 4k + 1$$$, для какого-то натурального $$$k$$$, и квадратичным невычетом тогда и только тогда, когда $$$p = 4k + 3$$$, для какого-то натурального $$$k$$$.
Очевидно, что сложность проверки числа $$$O(\log_2p)$$$.
Нахождение $$$i$$$ по модулю $$$p$$$
Опр. $$$i$$$ это такое число, что $$$i^2 = -1$$$ $$$\implies$$$ $$$i$$$ по модулю $$$p$$$ назовём такое число, что $$$i ^ 2 \equiv -1 \pmod{p}$$$.
Опр. Показателем числа $$$a$$$ по модулю $$$p$$$ назовём минимальное число $$$t$$$ такое, что $$$a^t \equiv 1 \pmod{p}$$$.
Теорема: $$$a^x \equiv 1 \pmod{p}$$$ тогда и только тогда, когда $$$a$$$ не делится на $$$p$$$ и $$$x$$$ делится $$$t$$$ (показатель $$$a$$$ по модулю $$$p$$$).
Алгоритм: Если $$$p = 4k + 3$$$ для какого-то натурального $$$k$$$, то такого $$$i$$$ не существует. Иначе рассмотрим число $$$a$$$, такое, что его показатель делится на $$$4$$$ и не делится на большие степени двойки (показатель далее будет обозначаться $$$t$$$). Так как у любого квадратичного вычета ровно $$$2$$$ корня, а у $$$1$$$ это $$$1$$$ и $$$-1$$$, то $$$a^{\frac{t}{2}} \equiv -1 \pmod{p}$$$, так как $$$t$$$ показатель, то $$$1$$$ быть не может. Значит $$$a^{\frac{t}{4}} \equiv i \pmod{p}$$$. Пусть $$$q = \frac{p - 1}{2^k}$$$, где $$$k$$$ степень вхождения $$$2$$$ в $$$p - 1$$$, тогда вместо $$$t$$$ можно использовать $$$4q$$$, так как $$$4q$$$ делится на $$$t$$$, а $$$2q$$$ нет. Осталось только найти подходящее $$$a$$$. Давайте выберем случайное $$$1 \le a \le p - 1$$$ и проверим, что $$$a^{2q} \equiv -1 \pmod{p}$$$, если это так, то $$$i \equiv a^q \pmod{p}$$$, иначе возьмём другое $$$a$$$. Ожидаемое время работы алгоритма — $$$O(\log_2p)$$$.