AT_arc149_f [ARC149F] Rational Number System

[problemUrl]: https://atcoder.jp/contests/arc149/tasks/arc149_f $ 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|\ かつ\ (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\ . $

入力は以下の形式で標準入力から与えられます． > $ p $ $ q $ $ N $ $ L $ $ R $

$ R-L+1 $ 行出力してください．$ i $ 行目には，$ N $ 以下の正整数全体を，$ \frac{p}{q} $ 進法展開の辞書順が小さい方から順に並べたとき，$ L\ +\ i\ -\ 1 $ 番目に並ぶ正整数を出力してください． 正整数の出力には $ 10 $ 進法表記を用いてください．

### 制約 - $ 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 $ ### Sample Explanation 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). ``` ### Sample Explanation 2 $ 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 $ から分かります． ### Sample Explanation 3 入力例 2 の出力のうち $ 3 $ 番目から $ 8 $ 番目が答となります．