По заданному n посчитать количество различных красивых последовательностей, которые из него можно получить (любой язык)

Задача D: Системы счисления
Сегодня Егор в школе проходил системы счисления, ему дали следующее определение представление числа в системе счисления:

Представлением целого положительного числа n в k-ичной системе счисления (k ≥ 2) называется последовательность целых неотрицательных чисел a1, ..., as такая, что ai ≤ k - 1 для всех i = 1...s и a1 ≠ 0, а также as + as - 1 · k + as - 2 · k2 + ... + a1 · ks - 1 = n.

Например, представлением числа 6 в двоичной системе счисления является последовательность 1, 1, 0, т.к. 0 + 1 · 2 + 1 · 4 = 6, а представлением числа 120 в одиннадцатиричной системе счисления является последовательность 10, 10, т.к. 10 + 10 · 11 = 120.

Можно показать, что любое целое положительное число n представимо единственным образом в k-ичной системе счисления для любого k ≥ 2.

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

Однако, так как число n очень большое, без программирования ему не обойтись. К сожалению, программировать он не умеет, поэтому обратился за помощью к вам. Напишите программу, которая по заданному n считает количество различных красивых последовательностей, которые из него можно получить.

Формат входных данных
В единственной строке входных данных находится единственное целое число n (1 ≤ n ≤ 1018) – число, которое увидел Егор, идя из школы.

Обращаем внимание, что входные данные в этой задаче могут не поместиться в 32-битный целочисленный тип данных вашего языка, рекомендуется использовать 64-битный тип данных (long long, int64_t языка С++, int64 языка Free Pascal, long языка Java и т.д.)

Формат результата
Выведите единственное число – ответ на задачу.

0

Самый простой способ - перебирать основание, k, от 2 до N-1. Если в конце два нуля, то инкрементируем счетчик.
Другой способ - посложней. Т.к. в конце должно быть два нуля, то получаем, что число должно нацело делиться на k². Следовательно, перебирать нам придется лишь такие k, которые удовлетворяют этому требованию. Если разбить число на простые множители, можно быстренько составить все возможные варианты k.

1

Если не сложно можно код (любой язык)

0

Да легко:
1. Получаем упорядоченный массив простых множителей числа N. google в помощь, алгоритмов навалом.
2. Проходимся по этому массиву и ищем те множители, которых больше одного. Из них и формируем k. Проверяем, выводим на печать при необходимости. Скажем, нашли мы, что множитель 7 встречается 5 раз. ОК, это значит, что k нельзя брать равным семи (т.к. у нас будет больше двух нулей), зато можно взять его равным 7²=49. В сорокадевятиричной системе наше число должно дать два нуля в хвосте. Смотрим дальше. Скажем, 11 встречается два раза. ОК - то, что надо! Значит, четко в одинадцатиричной системе будет два нуля. Допустим, что 13 встречается три раза → не подходит, т.к. в 13-ричной системе мы получим три нуля, а в 169-чной - только один.

Естественно, из парных множителей тоже можно составлять новые основания. Из примера выше это будет 49*11=539. Ну и так далее.

Можно упростить алгоритм: не подыскивать подходящие основания (зато в этом случае не нужно будет проверять!), а тупо перебирать все комбинации из множителей в качестве основания системы счисления. Правда, это будет ооочень долго.

1