ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Открытое личное первенство УрГУ 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Чокнутый профессор

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Профессор Натан Матанович просто одержим математикой. Он зачем-то стал выписывать на доске по порядку все целые положительные числа, начиная с единицы. После того, как на доске появляется очередное число a, профессор соединяет его отрезками со всеми написанными ранее числами b такими, что выполняется хотя бы одно из двух условий:
  • b + a · a ≡ 0 (mod k),
  • a + b · b ≡ 0 (mod k),
где k — некоторый заданный параметр.
И никто не смог уговорить его прекратить это бессмысленное занятие. Он сказал, что остановится лишь тогда, когда в графе чисел на доске появится цикл. Но когда это произойдёт и произойдёт ли вообще, известно только ему одному. Помогите его коллегам определить, после какого числа профессор остановится.

Исходные данные

В единственной строке дано целое число k (1 ≤ k ≤ 100000).

Результат

Если в графе на доске рано или поздно появится цикл, выведите число, после выписывания которого это произойдёт. Если же цикл в таком графе не появится никогда, выведите −1.

Пример

исходные данныерезультат
2
5

Замечания

В примере после того, как профессор выписал все числа от 1 до 4, граф содержит рёбра (1, 3) и (2, 4). Написав число 5, профессор соединяет его отрезками с числами 1 и 3, таким образом, в графе появляется цикл 1-5-3-1.
Автор задачи: Павел Егоров
Источник задачи: Открытое личное первенство УрГУ 2009 (28 февраля 2009)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1682. Чокнутый профессор