2301. 魔法松鼠哈利的金币袋
1000ms
256MB
简单
简单数学
题目描述
在魔法森林里，有一只名叫哈利的聪明松鼠。哈利发现了一个神秘的宝藏点，里面装满了各种面值的魔法金币。这些金币的面值非常奇特，都是某个正整数 $k$ 的幂次方（即 $k^0, k^1, k^2, k^3, \dots$ 元）。
由于每个面值的金币袋在宝藏点里都只有独一无二的一袋，哈利每次带走金币时必须遵守以下规则：
1. 每种面值的金币袋**最多只能拿一袋**（拿或者不拿）。
2. 哈利带走的总金额就是他挑选的这些金币袋的面值之和。
如果把哈利所有可能带走的不同总金额按从小到大的顺序排成一个神奇的递增序列：
当 $k = 3$ 时，这个序列是：
$$1, 3, 4, 9, 10, 12, 13, \dots$$
其对应的金币组合为：
$$3^0, 3^1, 3^0 + 3^1, 3^2, 3^0 + 3^2, 3^1 + 3^2, 3^0 + 3^1 + 3^2, \dots$$
哈利想知道，这个序列里的第 $N$ 项（即第 $N$ 小的总金额）是多少？请你写个程序帮它用 10 进制数表示出来。
输入格式
一行，包含两个由空格隔开的正整数 $k$ 和 $N$ ($3 \le k \le 15, \quad 10 \le N \le 1000$)。
输出格式
一行，输出一个正整数，表示序列的第 $N$ 项。要求整数前不要有空格和其他符号。
样例 1
输入 (Input)
3 100
输出 (Output)
981
- 对于所有数据：$3 \le k \le 15$，$10 \le N \le 1000$。
- **样例解释**：
当 $k = 3$ 时，第 $100$ 项对应的金额是 $981$。
- **算法提示**：
仔细观察序列的构成方式与二进制的对应关系：
- 第 1 项：$k^0$（二进制 `1` 对应第 0 位为 1）
- 第 2 项：$k^1$（二进制 `10` 对应第 1 位为 1）
- 第 3 项：$k^0 + k^1$（二进制 `11` 对应第 0、1 位为 1）
- 第 4 项：$k^2$（二进制 `100` 对应第 2 位为 1）
- 也就是说，第 $N$ 项的值实际上就是**把 $N$ 转化为二进制数后，再把这个二进制数当成 $k$ 进制数转换回十进制**。
- **数据溢出提示**：
当 $k = 15, N = 1000$ 时，结果会非常大。$1000$ 的二进制为 `1111101000`，在 15 进制下的计算结果会超出 32 位整型（`int`）的范围。**必须使用 64 位整型（C++ 中的 `long long`）进行存储与计算**。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功