分数: 900 点
问题陈述
让 r > 1 是一个有理数,并且 p 和 q 是分子和分母 分别是 r。也就是说, p 和 q 是正整数,使得 r = \frac{p}{q} 和 \gcd(p,q) = 1.
让 基地-\boldsymbol{r} 扩展 为正整数 n 是整数序列 (a_1, \ldots, a_k) 满足以下所有条件。
- a_i 是介于 0 和 p-1.
- a_1\neq 0.
- n = \sum_{i=1}^k a_ir^{k-i}.
可以证明任意正整数 n 有一个独特的基础-r 扩展。
给你正整数 p, q, N, L,和 R。在这里, p 和 q 满足 1.01 \leq \frac{p}{q}.
考虑对所有不大于的正整数进行排序 N 按其基数的字典升序排列-\frac{p}{q} 扩展。找到 L-th, (L+1)-th, \ldots, R此列表中的第一个正整数。
与往常一样,正整数的输入和输出使用十进制表示法。
序列的字典顺序是什么?
一个序列 当满足以下条件时, A = (A_1, \ldots, A_{|A|}) 据说是 按字典顺序较小 比 B = (B_1, \ldots, B_{|B|}) 当满足以下 1. 或 2. 时。在这里, |A| 和 |B| 表示的长度 A 和 B。
- |A|<|B| 和 (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
- 有一个整数 1\leq i\leq \min\{|A|,|B|\} 满足以下两个条件。
- (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
- A_i < B_i.
约束
- 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
输入
输入由标准输入按以下格式给出:
p q N L R
输出
打印 R-L+1 行。的 i- 第行应包含 (L + i - 1)- 不大于的所有正整数列表中的第一个正整数 N 按其基数的字典升序排序\frac{p}{q} 扩展。
使用十进制表示法打印正整数。
示例输入 1
3 1 9 1 9
示例输出 1
1 3 9 4 5 2 6 7 8
基地-3 正整数的扩展不大于 9 如下。
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
3 2 9 1 9
示例输出 2
1 2 3 4 6 9 7 8 5
基地-\frac32 正整数的扩展不大于 9 如下。
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).
可以看到,基地-\frac32 扩展 6 is (2,1,0),例如,来自 2\cdot \bigl(\frac32\bigr)^2 + 1\cdot \frac32 + 0\cdot 1 = 6.
示例输入 3
3 2 9 3 8
示例输出 3
3 4 6 9 7 8
这是 3-rd 通过 8输出到样本输入 2 的第行。
示例输入 4
10 9 1000000000000000000 123456789123456789 123456789123456799
示例输出 4
806324968563249278 806324968563249279 725692471706924344 725692471706924345 725692471706924346 725692471706924347 725692471706924348 725692471706924349 653123224536231907 653123224536231908 653123224536231909