Interval#4902

Interval

1 saniyə

64 meqabayt

Çətin

Bağlı interval $[X, Y]$ [X, Y] daxilində olan və $b$ ədədinin müxtəlif qüvvətlərinin cəmi kimi ifadə edilə bilən ədədlərin sayını tapın. Burada hər hansı bir $Z$ ( $X \leq Z \leq Y$ X \le Z \le Y) ədədini ifadə etmək üçün $b$ ədədinin hər bir qüvvəti yalnız bir dəfə istifadə oluna bilər.

Yəni, $[X, Y]$ [X, Y] intervalında aşağıdakı qayda ilə ifadə edilə bilən ədədlərin sayını hesablayın:

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,

harada hər $a_{i} \in {0, 1}$ a_i \in \{0, 1\}.

Giriş

Girişin ilk sətrində üç ədəd $X$ , $Y$ və $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) verilir; ədədlər boşluqla ayrılmışdır.

Çıxış

$[X, Y]$ [X, Y] intervalında $b$ ədədinin müxtəlif qüvvətlərinin cəmi kimi ifadə edilə bilən ədədlərin sayını çap edin.

Nümunələr

Nümunə 1

Qeyd

$X = 4$ X = 4, $Y = 10$ Y = 10, $b = 3$ b = 3 üçün ədədlər:

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 üçün ədədlər:

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]

X \leq Z \leq Y

[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} .