Рассмотрим натуральные числа A и B. Вам следует представить число A в виде алгебраической суммы целочисленных степеней числа B с наименьшим количеством слагаемых. Другими словами,
где s[i]
= -1 or s[i]
= 1, k[i]
- целые, n должно быть минимизировано.
Первая строка содержит натуральное число A без ведущих нулей. A содержит не более 3000 цифр. Вторая строка содержит целое число B (1 ≤ B ≤ 10^6
).
Вывести одно целое число n.