Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы --> Простые числа и разложение на множители
---> 2 задач <---
Источники --> Личные олимпиады --> Открытая олимпиада школьников
    2002(9 задач)
    2003(10 задач)
    2004(13 задач)
    2005(12 задач)
    2006(12 задач)
    2007(11 задач)
    2008-2009(19 задач)
    2009-2010(23 задач)
    2010-2011(19 задач)
    2011-2012(8 задач)
    2012-2013(21 задач)
    2013-2014(8 задач)
    2014-2015(8 задач)
Страница: 1 Отображать по:
#1009
Степень
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
32 megabytes
По заданному числа A необходимо найти минимальное N, такое, что N^N кратно A

Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу – для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.

Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.

Входные данные

Во входном файле содержится единственное число A (1 ≤ A ≤ \(10^9\) – на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…).

Выходные данные

В выходной файл вывести единственное число N.

Примеры
Входные данные
1
Выходные данные
1
Входные данные
8
Выходные данные
4
#1940
Последовательность-2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность.

Сначала он пишет на доске натуральное число \(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
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест