eolymp
bolt
Try our new interface for solving problems
Məsələlər

Экспоненциальные башни

Экспоненциальные башни

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Число 729 может быть записано в виде степени несколькими способами: 3^6, 9^3 и 27^2. Конечно, его можно записать как 729^1, но это не считается степенью. Мы хотим пойти еще дальше. Для удобства бдем использовать ^ для возведения в степень, поэтому определим a^b = a^b. Тогда число 256 можно также записать как 2^2^3 или 4^2^2. Напомним, что ^ является правоассоциативным, поэтому 2^2^3 означает 2^(2^3).

Определим башню степеней высоты k как выражение вида a[1]^a[2]^a[3]^.. ^a[k], где k > 1, целые числа a[i] > 1.

По заданной башне степеней высоты 3, представляющую некоторое целое число n, определите количество башен степеней высоты не более 3, которые представляют n.

Giriş verilənləri

Состоит из нескольких тестов, каждый содержится в отдельной строке. Каждый тест имеет формат a^b^c, где a, b и c - целые числа, 1 < a, b, c9585.

Çıxış verilənləri

Для каждого теста выведите количество способов, которыми может быть представлено число n = a^b^c в виде башни из степеней высоты не более трех.

Магическое число 9585 выбрано так, чтобы результат всегда был меньше 2^63.

Nümunə

Giriş verilənləri #1
4^2^2
8^12^2
8192^8192^8192
2^900^576
Çıxış verilənləri #1
2
10
1258112
342025379
Mənbə 2013 ACM North Western European Regional Contest (NWERC), Ноябрь 24, Задача E