Имя: Пароль: Зарегистрироваться Восстановить пароль
11/09/2024 17:23:19

# Рабочее место участника

## Задачи

1891. Great Deceiver

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)

Once upon a time Baron Munchhausen traveled to the Moon. After that he often tells interesting stories about the Selenites. Recently Baron told us about their numeric system. They use a notation with negative radix!
Negative radix is quite hard for Humans, and even for Munchhausen. So, Baron did a trick to help himself on the Moon. He remembered all the numbers between 0 and n inclusively, which have the same notation for both Selenites’ negative radix -k and a more convenient positive radix k.
Munchhausen claims that he did that easily. But, you know, Baron can exaggerate a little. To catch him, you have to count how many numbers he must have remembered.
Note: the k-radix notation of a number x is a sequence of integers a_0,\ a_1,\ …,\ a_p such that 0\ ≤\ a_i\ <\ |k| and sum_{i=0}^p\ a_i\ *\ k^i\ =\ x.
Input
The single line of the input file contains two integer numbers n and k (1\ ≤\ n\ ≤\ 10^15, 2\ ≤\ k\ ≤\ 1\ 000).
Output
Output the number of numbers Baron Munchhausen must have remembered during his stay on the Moon.

Sample Input #1

21 3

Sample Output #1

9

Sample Input #2

21 2

Sample Output #2

8
In the first sample, Baron must have remembered numbers 0, 1, 2, 9, 10, 11, 18, 19 and 20.
For example, 19 has the same notation for both radix 3 and radix -3: 19\ =\ 201_3\ =\ 201_{-3}, while 7 has not: 7\ =\ 21_3\ =\ 111_{-3}.
In the second sample, the corresponding numbers are 0, 1, 4, 5, 16, 17, 20 and 21.
Source: ACM ICPC NEERC, 2012