Преобразование
(Время: 2 сек. Память: 16 Мб Сложность: 21%)
Требуется из числа 0 получить целое число N, используя минимальное количество действий. В качестве действия над числом разрешается использовать одно из следующих преобразований:
- умножить число на некоторое целое K;
- прибавить к числу единицу.
Например, при N=30 и K=3 достаточно сначала прибавить 1, затем дважды умножить на 3, потом прибавить 1 и еще раз умножить на 3. Всего получилось 5 действий, которые можно записать следующим образом: ((0+1)×3×3+1)×3 = 30.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N (0 ≤ N ≤ 109), во второй строке записано целое число K (2 ≤ K ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – минимальное количество операций, необходимых для получения числа N из числа 0.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 30
3 | 5 |
| 2 | 4
2 | 3 |
Система оценки
Решения, работающие только для N ≤ 106, будут оцениваться в 35 баллов.
Решения, работающие только для K ≤ 106, будут оцениваться в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
