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 翻译