kill2021

22.02.2021 08:42 •  Информатика

Задача 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 и т.д.)

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

В первом тесте единственные системы счисления, в которых у числа 8 есть нули на конце – двоичная и четверичная, но в двоичной оно заканчивается на 3 нуля, а в четверичной на 1, так что ни та, ни другая не подходит.

Во втором тесте можно получить последовательность 1, 1, 0, 0, переведя 12 в двоичную систему счисления.

В третьем тесте можно получить последовательность 1, 1, 0, 0, 1, 0, 0, переведя 100 в двоичную систему счисления, последовательность 4, 0, 0, переведя 100 в пятиричную систему счисления и последовательность 1, 0, 0, переведя 100 в десятичную систему счисления. Обратите внимание, что 101-ричная система счисления не подходит для числа 100, т.к. 100 представляется в 101-ричной системе счисления как последовательность из одного числа 100, последний элемент этой последовательности равен 100, а не 0.