Інтервал#4902

Інтервал

1 секунда

64 мегабайти

Складна

Визначте кількість цілих чисел у замкненому інтервалі $[X, Y]$ [X, Y], які можна представити у вигляді суми різних степенів числа $b$ ; тобто, кількість чисел $Z$ таких, що кожна степінь $b$ використовується не більше одного разу у представленні:

Z = a_{n} b^{n} + a_{n - 1} b^{n - 1} + \dots + a_{1} b^{1} + a_{0} b^{0},

Z = a_n b^n + a_{n-1} b^{n-1} + \dots + a_1 b^1 + a_0 b^0,

де $a_{i} \in {0, 1}$ a_i \in \{0, 1\}.

Вхідні дані

У першому рядку задано числа $X$ , $Y$ та $b$ ( $1 \leq X \leq Y \leq 1 0^{100}$ 1 \le X \le Y \le 10^{100}, $2 \leq b \leq 10$ 2 \le b \le 10), відокремлені пропусками.

Вихідні дані

Виведіть одне число — кількість чисел у $[X, Y]$ [X, Y], які можна представити у вигляді суми різних степенів $b$ .

Приклади

Приклад 1

Примітка

Для $X = 4$ X = 4, $Y = 10$ Y = 10, $b = 3$ b = 3 такі числа:

4910 = 3^{1} + 3^{0}, = 3^{2}, = 3^{2} + 3^{0} .

\begin{align*} 4 &= 3^1 + 3^0,\\ 9 &= 3^2,\\ 10 &= 3^2 + 3^0. \end{align*}

Для $X = 1$ X = 1, $Y = 12$ Y = 12, $b = 2$ b = 2 такі числа:

123456789101112 = 2^{0}, = 2^{1}, = 2^{1} + 2^{0}, = 2^{2}, = 2^{2} + 2^{0}, = 2^{2} + 2^{1}, = 2^{2} + 2^{1} + 2^{0}, = 2^{3}, = 2^{3} + 2^{0}, = 2^{3} + 2^{1}, = 2^{3} + 2^{1} + 2^{0}, = 2^{3} + 2^{2} .

\begin{align*} 1 &= 2^0,\\ 2 &= 2^1,\\ 3 &= 2^1 + 2^0,\\ 4 &= 2^2,\\ 5 &= 2^2 + 2^0,\\ 6 &= 2^2 + 2^1,\\ 7 &= 2^2 + 2^1 + 2^0,\\ 8 &= 2^3,\\ 9 &= 2^3 + 2^0,\\ 10 &= 2^3 + 2^1,\\ 11 &= 2^3 + 2^1 + 2^0,\\ 12 &= 2^3 + 2^2. \end{align*}

[X, Y]

Z = a_{n} b^{n} + a_{n - 1} b^{n - 1} + \dots + a_{1} b^{1} + a_{0} b^{0},

a_{i} \in {0, 1}

1 \leq X \leq Y \leq 1 0^{100}

2 \leq b \leq 10

[X, Y]

X = 4

Y = 10

b = 3

4910 = 3^{1} + 3^{0}, = 3^{2}, = 3^{2} + 3^{0} .

X = 1

Y = 12

b = 2

123456789101112 = 2^{0}, = 2^{1}, = 2^{1} + 2^{0}, = 2^{2}, = 2^{2} + 2^{0}, = 2^{2} + 2^{1}, = 2^{2} + 2^{1} + 2^{0}, = 2^{3}, = 2^{3} + 2^{0}, = 2^{3} + 2^{1}, = 2^{3} + 2^{1} + 2^{0}, = 2^{3} + 2^{2} .