Олимпиада проводится при поддержке Московского физико-технического института, Компьютерной компании НИКС, Компании Yandex
Информационная поддержка:
журнал "Мир ПК"
IV Открытая олимпиада школьников по программированию, 2009/10 учебный год
Задача H. Последовательность-2
| Имя входного файла: | h.in |
| Имя выходного файла: | h.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность. Сначала он пишет на доске натуральное число A. Каждое следующее число, выписанное им на доске, будет равно степени с основанием A и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:
x[1] = A, x[k + 1] = Ax[k], k > 0После этого он решил узнать элемент этой последовательности с минимальным номером, который бы делился на данное число N. Поскольку числа на доске могут быть довольно большими, без вашей помощи ему не обойтись.
Формат входных данных
Вводятся два натуральных числа A, N (1 ≤ A ≤ 109, 1 ≤ N ≤ 109).
Формат выходных данных
Если ни один элемент последовательности не делится на N, выведите 0. Иначе выведите минимальный номер элемента рассмотренной последовательности, делящегося на N.
Примеры
| h.in | h.out |
2 2 |
1 |
2 4 |
2 |