Опр. Пусть $$$p > 2$$$ простое число, тогда квадратичным вычетом по модулю $$$p$$$ назовём все $$$1 \le x \le p - 1$$$, такие, что уравнение $$$a^2 \equiv x \pmod{p}$$$ имеет решения и квадратичным невычетом иначе. Обратите внимание, что $$$0$$$ не является ни квадратичным вычетом, ни квадратичным невычетом.
Теорема: Квадратичных вычетов и крадратичных невычетов поровну.
Доказательство
Теорема: Обозначим за $$$B$$$ квадратичный вычет, а за $$$H$$$ квадратичный невычет, тогда:
Доказательство
С помощью этих двух теорем уже можно решить 103428K - Tiny Stars.