Задача №1940. Последовательность-2
Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность.
Сначала он пишет на доске натуральное число \(A\). Каждое следующее число, выписанное им на доске, будет равно степени с основанием \(A\) и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:
\(x[1] = A\),
\(x[k + 1] = A^{x[k]}\), \(k\) > 0
После этого он решил узнать элемент этой последовательности с минимальным номером, который бы делился на данное число \(N\). Поскольку числа на доске могут быть довольно большими, без вашей помощи ему не обойтись.
Вводятся два натуральных числа \(A\), \(N\) (\(1\) ≤ \(A\) ≤ \(10^9\), \(1\) ≤ \(N\) ≤ \(10^9\)).
Если ни один элемент последовательности не делится на \(N\), выведите 0. Иначе выведите минимальный номер элемента рассмотренной последовательности, делящегося на \(N\).
2 2
1
2 4
2