AT_arc149_f [ARC149F] Rational Number System

设 $r > 1$ 为有理数，$p$ 为 $r$ 的分子，$q$ 为 $r$ 的分母。即 $p, q$ 是正整数，满足 $r = \frac{p}{q}$ 且 $\gcd(p, q) = 1$。 正整数 $n$ 的 **$r$ 进制展开** 定义为满足以下所有条件的整数序列 $(a_1, \ldots, a_k)$： - $a_i$ 是 $0$ 到 $p-1$ 之间的整数； - $a_1 \neq 0$； - $n = \sum_{i=1}^k a_i r^{k-i}$。 可以证明，任意正整数 $n$ 都有唯一的 $r$ 进制展开。 ------ 给定正整数 $p, q, N, L, R$，其中 $p, q$ 满足 $1.01 \leq \frac{p}{q}$。 将所有不超过 $N$ 的正整数，按其 $\frac{p}{q}$ 进制展开的字典序从小到大排列，输出第 $L, L+1, \ldots, R$ 个正整数。 注意，正整数的输入输出均使用通常的十进制表示。 **什么是数列的字典序？** 设数列 $A = (A_1, \ldots, A_{|A|})$，$B = (B_1, \ldots, B_{|B|})$，若满足下列 1 或 2，则称 $A$ 的字典序小于 $B$： 1. $|A| < |B|$ 且 $(A_1, \ldots, A_{|A|}) = (B_1, \ldots, B_{|A|})$； 2. 存在整数 $1 \leq i \leq \min\{|A|, |B|\}$，同时满足： - $(A_1, \ldots, A_{i-1}) = (B_1, \ldots, B_{i-1})$； - $A_i < B_i$。

输入通过标准输入给出，格式如下： > $p$ $q$ $N$ $L$ $R$

输出 $R-L+1$ 行。第 $i$ 行输出所有不超过 $N$ 的正整数，按 $\frac{p}{q}$ 进制展开的字典序从小到大排列时，第 $L+i-1$ 个正整数。 输出正整数时请使用十进制表示。

### 约束条件 - $1 \leq p, q \leq 10^9$ - $\gcd(p, q) = 1$ - $1.01 \leq \frac{p}{q}$ - $1 \leq N \leq 10^{18}$ - $1 \leq L \leq R \leq N$ - $R - L + 1 \leq 3 \times 10^5$ ### 样例解释 1 $9$ 以下正整数的 $3$ 进制展开如下： ``` 1: (1), 2: (2), 3: (1, 0), 4: (1, 1), 5: (1, 2), 6: (2, 0), 7: (2, 1), 8: (2, 2), 9: (1, 0, 0)。 ``` ### 样例解释 2 $9$ 以下正整数的 $\frac{3}{2}$ 进制展开如下： ``` 1: (1), 2: (2), 3: (2, 0), 4: (2, 1), 5: (2, 2), 6: (2, 1, 0), 7: (2, 1, 1), 8: (2, 1, 2), 9: (2, 1, 0, 0)。 ``` 例如 $6$ 的 $\frac{3}{2}$ 进制展开为 $(2, 1, 0)$，因为 $2 \cdot \left(\frac{3}{2}\right)^2 + 1 \cdot \frac{3}{2} + 0 \cdot 1 = 6$。 ### 样例解释 3 输入样例 2 的输出中，第 $3$ 到第 $8$ 个即为答案。 由 ChatGPT 4.1 翻译