Квадрат в классе остатков

Если среди чисел есть данное CC, квадрат должен иметь тот же остаток по модулю MM. Остаток квадрата зависит только от остатка основания. Поэтому достаточно проверить основания от 0 до M−1M-1; это полная конечная область, охватывающая все целые числа.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 1. Если среди чисел есть данное CC, квадрат должен иметь тот же остаток по модулю MM. Остаток квадрата зависит только от остатка основания. Поэтому достаточно проверить основания от 0 до M−1M-1; это полная конечная область, охватывающая все целые числа.
C=431C=431
(0;1;4;5;9;16)\left(0;1;4;5;9;16\right)
r=11r=11

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу