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

1375. Нонконформизм

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Системному администратору со звучной фамилией Сидоренко не дают покоя дыры в системах безопасности операционных систем. Справедливо считая, что хорошо защищенная система должна быть оригинальной, он решил разработать новую схему шифрования с открытым/закрытым ключом. Сказано — сделано, пара ночей дудения в любимую админскую трубу, плясок с админским бубном, и придумана новая схема.
Открытым ключом в схеме Сидоренко оказалась пара чисел (k, p), причем p должно быть простым числом, и 0 ≤ kp−1. А закрытым ключом — пара (x, y). Относительно этих чисел должно выполняться такое соотношение:
x2 + y2 = k (mod p)
Сидоренко, конечно, и не думал, что его схема лучше RSA, зато изучена гораздо слабее.
Все было бы просто замечательно, если бы Сидоренко не обделил (несправедливо!) правами замечательного программиста Глюкова, не урезал ему жизненно необходимый интернет-трафик, не закрыл его любимые профессиональные сайты. В общем, плохо поступил Сидоренко, очень плохо. Одним словом, надо исправить сей досадный недочет. Для этого Глюкову нужно сделать сущую безделицу: по открытому сидоренковскому ключу восстановить его закрытый ключ. Но не дается Глюкову пароль админский…

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

Первая строка содержит два целых числа: k и p. Число p — простое, 2 ≤ p ≤ 106; 0 ≤ kp−1.

Результат

Через пробел выведите любую пару целых чисел x и y (0 ≤ xp−1, 0 ≤ yp−1), такую что x2 + y2 = k (mod p). Если такой пары не существует, выведите «NO SOLUTION».

Пример

исходные данныерезультат
1 3
0 2
Автор задачи: Ден Расковалов
Источник задачи: IX Чемпионат Урала по программированию. Екатеринбург, УрГУ, 19-24 апреля 2005г.