Автор: | Иван Кобец | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
Выходной файл: | Стандартный выход |
На днях в Логландии прошла вселогландская олимпиада школьников по математике. Мальчик Влад не смог пройти на заключительный этап этой олимпиады, но его очень заинтересовала одна задача c финала. Суть данной задачи следующая: дан отрезок целых чисел от 1 до n, необходимо определить количество различных чисел, которое можно представить в виде суммы одной или более неповторяющихся степеней k (т. е. чисел k1, k2, k3 и т. д.)
В первой строке входных данных записано два целых числа n и k.
Выведите одно число — количество различных чисел от 1 до n, которое можно представить в указанном виде.
1 ≤ n ≤ 1018
1 ≤ k ≤ 20
В первом примере мы может образовать из чисел 1, 3, 9, 27 следующие варианты: 1, 3, 4, 9, 10, 12, 13, 27, 28, 30.
Во втором примере мы можем представить все числа от 1 до 7.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|