Входной файл: input.txt Выходной файл: output.txt Время на тест: 1 секунда Ограничение на память: 16 MB Автор задачи: Метельский И.С. Авторское решение:Pascal Тесты к задаче:Скачать
После выполнения заказа от "Lavr" фирма "VasEk" стала всемирно известной. У нее появился сайт в Интернет www.vasek.gov.no (добро пожаловать!!!). Заказчики теперь должны регистрироваться на сайте, и только потом посылать заказ, заполняя специальную форму. При регистрации заказчик получает логин и пароль. Пароль является целым числом от 0 до M-1. На сервере пароли хранятся в зашифрованном виде. Для шифрования используется суперпуперхэш-функция EVP, работающая следующим образом: вместо числа X хранится EVP(X)=(X^2) mod M. На данный момент используется значение M=35.
Недавно на e-mail "Василия" vasek@gov.no пришло сообщение следующего содержания:
"У вас отстойная система безопасности. Мой пароль - 6. Мой друг ввел мой логин и первый попавшийся пароль - 1. Почему-то этот фокус прошел, и друг получил доступ к моей информации. Разберитесь, в чем дело."
"Василий" начал думать, и через несколько дней понял, в чем дело. Дело в том, что EVP(6)=1 и EVP(1)=1, поэтому система не может отличить пароли 1 и 6 друг от друга. Собрав совет фирмы, "Василий" решил усилить систему безопасности следующим образом:
1) Изменить значение M.
2) Запретить использование паролей X, для которых EVP(X)=1.
Все остальные 0 программистов фирмы согласились с "Василием". Теперь, когда уже известно новое значение M, необходимо только найти все X, для которых EVP(X)=1.
Задание.
По введенному M найдите все X, для которых EVP(X)=1.Как было сказано выше, 0<=X<=M-1.
Ввод.
Единственная строка входного файла содержит число M.
Вывод.
Выведите все X (0<=X<=M-1), для которых EVP(X)=1 по одному в строке в порядке возрастания.