Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1701. Теорема Васи
Модулярная арифметикаОлимпиадные задачи на русском языке
| 02/12/2011 | Муниципальный этап 9-11 классы (3) |
| 27/06/2018 | Лето 2018 - 2 (упрощенное) (A) |
| 02/07/2020 | Лето 2020 - 2 (упрощенное) (A) |
Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0) 
Третьеклассник Вася прочитал про теорему Ферма и придумал свою теорему:
«Для любых натуральных чисел `a>1` и `b>1` найдется бесконечно много натуральных чисел `n` таких,
что `a^n\ +\ b^n` делится на `n` без остатка».
Напишите программу, которая найдет для заданных `a` и `b` все числа `n`, не превосходящие `M`,
для которых выполняется свойство из теоремы Васи. При проверке делимости некоторого выражения на `n` можно
все вычисления в этом выражении выполнять с остатками от деления на `n`:
`(x+y)\ mod\ n\ =\ ((x\ mod\ n)\ +\ (y\ mod\ n))\ mod\ n`
`(x*y)\ mod\ n\ =\ ((x\ mod\ n)\ *\ (y\ mod\ n))\ mod\ n`
`(x^n)\ mod\ n\ =\ (…((((1\ *\ x)\ mod\ n)\ *\ x)\ mod\ n)…\ *\ x)\ mod\ n`
В первой строке содержатся три целых числа `a`, `b` и `M` (`2\ ≤\ a,\ b\ ≤\ 100`, `2\ ≤\ M\ ≤\ 100000`).
Вывести варианты `n` в диапазоне от 1 до `M` включительно в порядке возрастания,
для которых выполняется свойство, указанное в теореме Васи. Каждое значение вывести на отдельной строке.
Пример ввода
2 3 100
Пример вывода
1 5 25 55
