Hints → https://atcoder.jp/contests/arc149/editorial/4961

---

[1] The unique existence of base-\(r\) expansion

Let us first prove the unique existence of base-\(r\) expansion, which was also mentioned in the Problem Statement. We begin with showing the following:

• if \(n\) has a base-\(r\) expansion \((a_1, \ldots, a_k)\), then \(a_k = n\bmod p\).

Actually, by multiplying both sides of \(n = \sum_{i=1}^k a_ir^{k-i}\) by \(q^{k-1}\), one sees that \(p\mid q^{k-1}(n-a_k)\), so one obtains \(n\equiv a_k\pmod{p}\) from \(\gcd(p,q)=1\) (A simpler proof is possible by expanding the notion of “the remainder when divided by \(p\)” to rational numbers whose denominator is coprime with \(p\)).

From this, one also sees the following:

• if \(n = px + y\) (\(0\leq y\leq p-1\)) has a base-\(r\) expansion \((a_1, \ldots, a_k)\), then \(a_k=y\), and the prefix \((a_1, \ldots, a_{k-1})\) is an empty sequence or the base-\(r\) expansion of \(qx\).

This inductively shows the unique existence of base-\(r\) expansion.

---

[2] The trie structure

To study the order by base-\(r\) expansion, let us use a trie. As seen in the proof in [1], the base-\(r\) expansion of \(n = px + y\) is the base-\(r\) expansion of \(qx\) with \(y\) appended to the end, so let us span an edge from \(qx\) to \(px+y\) to construct a trie. The figure below shows the trie when \(r = 3/2\).

One can also see that the integers corresponding to the nodes in the trie match the BFS order.

Let us evaluate the depths of the nodes with integers at most \(N\). The depth \(k\) is the length of the base-\(r\) expansion, so we have \(r^{k-1}\leq N\), that is, \(k\leq 1 + \log_{r}N\). Under the constraints of this problem, \(k\leq 1 + \log_{1.01}(10^{18}) = 4166.342\cdots\).

Below, let \(D\) denote the depth of the trie.

---

[3] Computing the answer

The lexicographical order on base-\(r\) expansions matches the pre-order in DFS on the trie. Thus, one can perform DFS on the trie and report the \(L\)-th, \(\ldots\), \(R\)-th nodes to solve the problem in \(O(N)\) time.

Let us optimize this DFS. If the \(L\)-th node is found, one can compute the \((L+1)\)-th, \(\ldots\), \(R\)-th nodes by a simple DFS in a total of \(O(R-L+D)\) time, so let us concentrate on the \(L\)-th node.

Since the depth of the trie is \(D\), we need to do the following \(D\) times:

• from some node in the trie, find which of its children has the sought node in its subtree.

If we use binary search to find this, we want to do the following fast enough:

compute the sum of the sizes of the subtrees of the first \(n\) children of some node in the trie.

Since the integers corresponding to the nodes in the trie match the BFS order, the set of integers corresponding to the nodes in a subtree at a fixed depth form an interval. Thus, by finding the lower and upper limits of that interval, one can compute the number of nodes at a fixed depth. By doing this for every depth, one can solve the problem above in \(O(D)\) time.

By summarizing all of the above, the original problem can be solved in \(O(D^2\log p + R-L)\) time.

---

Sample submission

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