まず、\(A\) を \(f(A)\) に取り換える操作回数について、\(N\) 回という値に大きな意味はありません。操作は十分大きな回数行うと考え、以後操作回数への言及は行いません。

---

◆ 係数列

挿入操作によって、数列 \(A\) は次のように変化していきます。

• \(a, b\)
• \(a, a+b, b\)
• \(a, 2a+b, a+b, a+2b, b\)
• \(a, 3a+b, 2a+b, 3a+2b, a+b, 2a+3b, a+2b, a+3b, b\)
• \(\vdots\)

このようにすべての項が \(xa + yb\) の形で表せるので、それぞれの項に対する係数 \((x, y)\) の列を考えます。

• \((1, 0), (0, 1)\)
• \((1, 0), (1,1), (0, 1)\)
• \((1, 0), (2,1), (1,1), (1,2), (0, 1)\)
• \((1, 0), (3,1), (2,1), (3,2), (1,1), (2,3), (1,2), (1,3), (0, 1)\)
• \(\vdots\)

こうして得られる \(2\) 数の組の列を、以降単に「係数列」と呼ぶことにします。

係数列の性質

次を示すことができます。

[係数列の性質 (1)] 挿入操作を何回か行った時点の係数列で \((x_1, y_1)\), \((x_2,y_2)\) が隣り合うならば、\(x_1y_2 - x_2y_1 = 1\) が成り立つ。

証明は帰納法により容易です。逆に、次を示すこともできます。

[係数列の性質 (2)] \(0\leqq x_1,y_1,x_2,y_2\) に対して \(x_1y_2 - x_2y_1 = 1\) が成り立つならば、挿入操作を何回か行った時点の係数列で \((x_1, y_1)\), \((x_2,y_2)\) が隣り合う。

例えば、\(x_2 + y_1\) に関する帰納法により証明できます。\(x_2 + y_1 > 0\) かつ \(x_1y_2 - x_2y_1 = 1\) のとき、

• \(x_1\leqq x_2\) かつ \(y_1\leqq y_2\)
• \(x_1\geqq x_2\) かつ \(y_1\geqq y_2\)

のいずれかが成り立つことが証明できます。前者の場合には \((x_3, y_3) = (x_2 - x_1, y_2 - y_1)\) とすれば、\(x_3, y_3\geqq 0\) かつ \(x_1y_3 - x_3y_1 = 1\) となり、帰納法の仮定より \((x_1,y_1)\) と \((x_3,y_3)\) は挿入操作を何回か行った時点の係数列で隣り合います。その次の操作でこれらの間に \((x_2, y_2)\) が挿入されます。後者の場合も同様に証明できます。

これらの性質から、次が分かります。

[係数列の性質 (3)] \(\gcd(x,y) = 1\) となる非負整数の組 \((x,y)\) は、挿入操作を何回か行った時点での係数列に現れる。

[係数列の性質 (4)] どの時点での係数列においても、組 \((x,y)\) は \(y/x\) について昇順に並ぶ（ただし、\((x,y) = (0,1)\) の場合には \(y/x=\infty\) として扱う）。

---

◆ 数列 \(B\) の言い換え

結局、数列 \(B\) は次のようなものであることが分かります。

\(ax + by\leqq N\) を満たす非負整数のうちで、\(\gcd(x,y) = 1\) を満たすものを考える。 そのような組 \((x,y)\) を \(y/x\) の昇順にソートして、\(i\) 番目の組を \((x_i, y_i)\) とするとき \(B_i = ax_i + by_i\) が成り立つ。

---

◆ \(B_n\) の計算

まずは、ひとつの \(B_n\) を計算するという部分問題を解くことにします。二分探索と合わせて、次の数え上げに帰着されます。

正の整数 \(a, b, N\) および有理数 \(c\) が与えられる。次の条件をすべて満たす非負整数の組 \((x,y)\neq (0,0)\) を数え上げよ：

• \(ax + by\leqq N\)
• \(\gcd(x,y) = 1\)
• \(y/x \leqq c\)

\(a, b, c\) を固定して、上記の数え上げの結果を \(f(N)\) と表すことにします。また、\(\gcd(x, y) = 1\) という条件を無視して数え上げた結果を \(F(N)\) と書くことにします。組 \((x,y)\) を \(\gcd(x,y) = d\) ごとに分類して数え上げることで、\(F(N) = \sum_{d=1}^N f(\lfloor N/d\rfloor)\) が成り立ちます（\(\gcd(x,y)\) による分類を簡潔にするため、組 \((x,y) = (0,0)\) を除いておきました）。

Möbius の反転公式により、\(f(N) = \sum_{d=1}^N \mu(d)F(\lfloor N/d \rfloor)\) が成り立ちます。このことを利用して、\(f(N)\) を計算することができます。

\(F(1), F(2), \ldots, F(N)\) は累積和などを用いて合計 \(O(N)\) 時間で計算できるので、\(f(N)\) の計算量はメビウス関数の前計算のもと \(O(N)\) 時間で行えます。

二分探索と合わせることで、ひとつの項 \(B_n\) の計算は \(O(N\log N)\) 時間で計算できることが分かりました。

---

なお、Möbius 関数の累積和を前計算のもと、各 \(F(n)\) を \(O(\log n)\) 時間で計算する（[AtCoder Library] floor_sum が利用できる）ことで、\(B_n\) の計算を \(O(N^{1/2}\log^2 N)\) 時間で行うこともできます。

---

◆ \(B_L, \ldots, B_R\) の計算

数列 \(B\) の構築手順を考えると、\(B_{n}, B_{n+1}\) が既知であるときに \(B_{n+2}\) を求めることが \(O(1)\) 時間でできます。したがって、\(B_L\), \(B_{L+1}\) さえ計算してしまいさえすれば、残りの \(B_i\) は合計 \(O(R-L)\) 時間で計算することができます。以上により本問題を解くことができました。

なお、\(L\), \(R\) に対する二分探索を合わせることで \(L\) 番目から \(R\) 番目までの係数 \((x, y)\) をまとめて列挙して、ソートすることでも解くことができます。

---

◆ 参考：Farey 数列との関係

\(0\) 以上 \(1\) 以下かつ、分母が \(N\) 以下の既約分数を昇順に並べた数列を、Farey 数列といいます。例えば以下の通りです。

• \(n = 1\) の場合：\(\frac01, \frac11\)
• \(n = 2\) の場合：\(\frac01, \frac12, \frac11\)
• \(n = 3\) の場合：\(\frac01, \frac13, \frac12, \frac23, \frac11\)
• \(n = 4\) の場合：\(\frac01, \frac14, \frac13, \frac12, \frac23, \frac34, \frac11\)
• \(n = 5\) の場合：\(\frac01, \frac15, \frac14, \frac13, \frac25, \frac12, \frac35, \frac23, \frac34, \frac45, \frac11\)

Farey 数列は、次のような手順で計算することができることが知られています（「係数列の性質」で行った議論がほとんどそのまま適用できます）：

• \(\frac{0}{1}, \frac{1}{1}\) から始める。
• \(\frac{y_1}{x_1}, \frac{y_2}{x_2}\) の間に \(\frac{y_1+y_2}{x_1+x_2}\) を挿入することを繰り返す

Farey 数列の計算方法は本解説における係数列の計算方法と酷似しており、実際、非負整数の組 \((x_1,y_1)\) と分数 \(\frac{x_1}{x_1+y_1}\) を対応させることで係数列と Farey 数列を対応づけることもできます。

---

より Farey 数列との関係を意識した、本問題の別の見方を紹介します。まず容易に \(\gcd(a, b) = 1\) の場合に帰着できるため、以降それを仮定します。

\(\gcd(a,b) = 1\) より、\(a'b - ab' = 1\) となる非負整数 \(a', b'\) をとることができます。

\((a, b)\) の代わりに \(2\) つの分数 \((a'/a, b'/b)\) を考えることとし、\(y_1/x_1, y_2/x_2\) の間に \((y_1+y_2)/(x_1+x_2)\) を挿入するという操作を考えることで、本問題の挿入操作を Farey 数列の計算手順と同一視することができます。したがって、本問題の数列 \(B\) は、

分母が \(N\) 以下で、\(a'/a\) 以上 \(b'/b\) 以下の既約分数 \(y/x\) を昇順に並べて、その分母 \(x\) のみを取り出したものが数列 \(B\) である

と言い換えることができます。例えば、\(a = 2, b = 1, N = 6\) とすると、

• 本問題の数列 \(B\)：\((2, 5, 3, 4, 5, 1) \)
• 分母が \(6\) 以下で \(1/2\) 以上 \(1/1\) 以下の既約分数を昇順ソートしたもの：\(\left(\frac12, \frac25, \frac23, \frac34, \frac45, \frac11\right)\)

となっています。

結局本問は、以下と同値であることが分かりました。

\(\frac{a'}{a}\) と \(\frac{b'}{b}\) の間にある分母が \(N\) 以下の既約分数を昇順に並べたとき、\(L\) 項目から \(R\) 項目までの分母を昇順に答えよ。