P2558 [AHOI2002] Network Transmission

In computer networks, all data are transmitted in binary form. However, when transmitting large data, directly sending its binary representation often requires too many bits. For example, transmitting $1024$ needs an $11$-bit binary number. Therefore, Xiao Keke proposed an idea for optimizing data transmission and plans to test it. The idea is: arrange in increasing order the sequence $\{a(k)_n\}$ consisting of all positive integer powers of $k$, as well as sums of any number of pairwise distinct powers of $k$. For example, when $k = 3$, the first $7$ terms of $\{a(k)_n\}$ are $1(=3^0)$, $3(=3^1)$, $4(=3^0+3^1)$, $9(=3^2)$, $10(=3^0+3^2)$, $12(=3^1+3^2)$, $13(=3^0+3^1+3^2)$. If a number $d$ is the $p$-th term of the sequence $\{a(k)_n\}$, then one can represent $d$ by transmitting the two numbers $k$ and $p$. Since the relatively small numbers $k$ and $p$ can represent a very large number, this can theoretically reduce the number of bits transmitted. Now Xiao Keke asks you to write a program to compute the number $d$ represented by the received $k$ and $p$.

A single line contains two positive integers $k$ and $p$, with $1 < k \le 1024$, $1 \le p \le 1024$.

Output the answer in one line (the number of digits does not exceed $50$).

Translated by ChatGPT 5