F - Rational Number System Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

r > 1 を有理数とし，p を r の分子，q を r の分母とします．つまり p, q は正整数で r = \frac{p}{q} かつ \gcd(p,q) = 1 が成り立つとします．

正整数 n の \boldsymbol{r} 進法展開 を，次の条件をすべて満たす整数列 (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, L+1, \ldots, R 番目に並ぶ正整数を答えてください．

なお，正整数の入出力には通常の 10 進法表記が用いられます．

数列の辞書順とは？

数列 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|\} が存在して，下記の 2 つがともに成り立つ．
    • (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 行目には，N 以下の正整数全体を，\frac{p}{q} 進法展開の辞書順が小さい方から順に並べたとき，L + i - 1 番目に並ぶ正整数を出力してください．

正整数の出力には 10 進法表記を用いてください．

入力例 1

3 1 9 1 9

出力例 1

1
3
9
4
5
2
6
7
8

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

3 2 9 1 9

出力例 2

1
2
3
4
6
9
7
8
5

9 以下の正整数の \frac32 進法展開は次の通りです．

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 の \frac32 進法展開が (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

入力例 2 の出力のうち 3 番目から 8 番目が答となります．

入力例 4

10 9 1000000000000000000 123456789123456789 123456789123456799

出力例 4

806324968563249278
806324968563249279
725692471706924344
725692471706924345
725692471706924346
725692471706924347
725692471706924348
725692471706924349
653123224536231907
653123224536231908
653123224536231909

Score : 900 points

Problem Statement

Let r > 1 be a rational number, and p and q be the numerator and denominator of r, respectively. That is, p and q are positive integers such that r = \frac{p}{q} and \gcd(p,q) = 1.

Let the base-\boldsymbol{r} expansion of a positive integer n be the integer sequence (a_1, \ldots, a_k) that satisfies all of the following conditions.

  • a_i is an integer between 0 and p-1.
  • a_1\neq 0.
  • n = \sum_{i=1}^k a_ir^{k-i}.

It can be proved that any positive integer n has a unique base-r expansion.

You are given positive integers p, q, N, L, and R. Here, p and q satisfy 1.01 \leq \frac{p}{q}.

Consider sorting all positive integers not greater than N in ascending lexicographical order of their base-\frac{p}{q} expansions. Find the L-th, (L+1)-th, \ldots, R-th positive integers in this list.

As usual, decimal notations are used in the input and output of positive integers.

What is lexicographical order on sequences?

A sequence A = (A_1, \ldots, A_{|A|}) is said to be lexicographically smaller than B = (B_1, \ldots, B_{|B|}) when 1. or 2. below is satisfied. Here, |A| and |B| denote the lengths of A and B, respectively.

  1. |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
  2. There is an integer 1\leq i\leq \min\{|A|,|B|\} that satisfies both of the following.
    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).
    • A_i < B_i.

Constraints

  • 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

Input

The input is given from Standard Input in the following format:

p q N L R

Output

Print R-L+1 lines. The i-th line should contain the (L + i - 1)-th positive integer in the list of all positive integers not greater than N sorted in ascending lexicographical order of their base-\frac{p}{q} expansions.

Use decimal notations to print positive integers.

Sample Input 1

3 1 9 1 9

Sample Output 1

1
3
9
4
5
2
6
7
8

The base-3 expansions of the positive integers not greater than 9 are as follows.

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).

Sample Input 2

3 2 9 1 9

Sample Output 2

1
2
3
4
6
9
7
8
5

The base-\frac32 expansions of the positive integers not greater than 9 are as follows.

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).

One can see that the base-\frac32 expansion of 6 is (2,1,0), for instance, from 2\cdot \bigl(\frac32\bigr)^2 + 1\cdot \frac32 + 0\cdot 1 = 6.

Sample Input 3

3 2 9 3 8

Sample Output 3

3
4
6
9
7
8

This is the 3-rd through 8-th lines of the output to Sample Input 2.

Sample Input 4

10 9 1000000000000000000 123456789123456789 123456789123456799

Sample Output 4

806324968563249278
806324968563249279
725692471706924344
725692471706924345
725692471706924346
725692471706924347
725692471706924348
725692471706924349
653123224536231907
653123224536231908
653123224536231909