← 返回题目列表

AtCoder · arc149_f

F. 有理数系统

中文机器翻译题面 查看原题

分数: 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。

  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.

约束

  • 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