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

1456. Джедайский ребус 2

Ограничение времени: 0.25 секунды
Ограничение памяти: 64 МБ

Вступление

Каждому человеку хочется стать уважаемым и знаменитым. При этом многие забывают, что большинство людей становятся уважаемыми и знаменитыми лишь после собственной смерти. Взять к примеру системного администратора Василия "Jedi Master" Тапкина. Впервые его имя было упомянуто в связи с нашумевшим делом о расшифровке пароля. Тогда за доступ к одному архиву с ценнейшей информацией боролась чуть ли не половина человечества (более подробно эта история описана в задаче "Джедайский ребус").
После этого случая неординарной личностью г-на Тапкина и его научными исследованиями заинтересовались крупнейшие мировые светила криптографии. Изучение обширного творческого наследия, оставленного Василием, показало, что последние годы своей жизни он потратил на постижение самой природы Силы. Г-н Тапкин пытался отыскать легендарное Число Силы. В XII томе "Книги Света и Тьмы" сохранилось подробное описание поражающего воображение эксперимента:

Задача

"...И взял я Число Света A и Число Тьмы N. Но Тьма и Свет неразделимы, и взял я Единицу, ибо непознанна и священна суть Её. И умножил я Единицу на Число Света, а полученное поделил на Число Тьмы, взяв Остаток от этого деления Z[1] = (1*A) modulo N. После этого я умножил Остаток на Число Света и поделил результат на Число Тьмы, вновь взяв Остаток от деления Z[2] = (Z[1]*A) modulo N. В величайшем нетерпении я снова и снова перемножал, делил и получал всё новые и новые Остатки Z[i]... И в один из дней понял я, как был слеп. Единица есть ключ к Силе, Начало и Конец Её. С утроенным рвением я вернулся к работе. Ибо знал я - Число Силы X будет найдено лишь тогда, когда очередной Остаток Z[X] обратится в Единицу. И да пребудет со мною Сила..."

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

Единственная строка содержит целые Числа A и N (2 ≤ A < N ≤ 109).

Результат

Вывести наименьшее положительное Число X, если оно существует. Иначе вывести ноль.

Пример

исходные данныерезультат
7 20
4

Замечания

В примере Остатки Z[1] = (1*7) modulo 20 = 7, Z[2] = (7*7) modulo 20 = 9, Z[3] = (9*7) modulo 20 = 3 и Z[4] = (3*7) modulo 20 = 1.
Автор задачи: Илья Гребнов, Дмитрий Ковалёв, Никита Рыбак
Источник задачи: Timus Top Coders: Second Challenge