ヒント → https://atcoder.jp/contests/arc149/editorial/4868

---

[1] \(r\) 進法展開の一意存在について

まずは問題文でも述べられていた，\(r\) 進法展開の一意存在を証明しておきます．まず，次を示すことができます：

• \(n\) が \(r\) 進法展開 \((a_1, \ldots, a_k)\) を持つならば，\(a_k = n\bmod p\)．

実際，\(n = \sum_{i=1}^k a_ir^{k-i}\) の両辺に \(q^{k-1}\) をかけた式から \(p\mid q^{k-1}(n-a_k)\) が分かるので，\(\gcd(p,q)=1\) より \(n\equiv a_k\pmod{p}\) が得られます（「\(p\) で割った余り」の概念を分母が \(p\) と互いに素な有理数について拡張してより簡潔に示すこともできます）．

このことからさらに，

• \(n = px + y\) （\(0\leq y\leq p-1\)）が \(r\) 進法展開 \((a_1, \ldots, a_k)\) を持つならば，\(a_k=y\) であり，その prefix \((a_1, \ldots, a_{k-1})\) は空列または \(qx\) の \(r\) 進法展開である．

ことが分かり，帰納的に \(r\) 進法展開の一意存在が分かります．

---

[2] Trie の構造

\(r\) 進法展開による順序を調べるために，Trie を考えます．[1] での証明から分かるように，正整数の \(n = px + y\) の \(r\) 進法展開は \(qx\) の \(r\) 進法展開の末尾に \(y\) を加えたものであることが分かるので，\(qx\) から \(px+y\) に辺を張ることで Trie を構築できます．次の図は，\(r = 3/2\) の場合の Trie を図示したものです．

さらに，Trie の各ノードに対応する整数は，そのノードの bfs 順に一致することも分かります．

\(N\) 以下の整数のノードの深さを評価しておきましょう．深さ \(k\) は \(r\) 進法展開の長さなので，\(r^{k-1}\leq N\) が成り立ち，\(k\leq 1 + \log_{r}N\) が成り立ちます．本問題の制約のもと，\(k\leq 1 + \log_{1.01}(10^{18}) = 4166.342\cdots\) 程度です．

以下，Trie の深さを \(D\) で表します．

---

[3] 答の計算

\(r\) 進法展開の辞書順は，Trie を dfs するときの preorder と一致します．よって Trie を dfs して \(L, \ldots, R\) 番目を答えれば，\(O(N)\) 時間で本問題を解くことができます．

この dfs を高速化しましょう．\(L\) 番目のノードが分かれば \(L+1, \ldots, R\) 番目のノードは単純な dfs で合計 \(O(R-L+D)\) 時間で計算できるため，\(L\) 番目のノードを計算する方法を考えればよいです．

Trie の深さは \(D\) なので，次のような計算を \(D\) 回行えばよいです：

Trie のあるノードに居るときに，どの子の部分木に目的のノードがあるかを調べる

これを二分探索で計算することを考えれば，次が十分高速に行えればよいことになります：

Trie のあるノードの子ノードのうちはじめの \(n\) 個について，部分木の大きさの総和を計算する．

Trie のノードに対応する整数が Trie の bfs 順であることから，部分木内のノードに対応する整数全体は，深さを固定すると区間の形になっています．よってその区間の下限・上限を求めることで深さを固定した場合のノードの個数を計算できます．これをすべての深さに対して計算することで，この問題は \(O(D)\) 時間で解くことができます．

以上をまとめると，本問題は \(O(D^2\log p + R-L)\) で解くことができます．

---

解答例

https://atcoder.jp/contests/arc149/submissions/35220969