Hints: https://atcoder.jp/contests/arc166/editorial/7374

[1] Maximizing \(R-L\)

If \((L,R)\) satisfies \(n_a-n_b\leq n\), then one of \((L,R), (L,R+1), (L,R+2),\ldots\) satisfies \(n_a-n_b=n\). Therefore, replacing the condition \(n_a-n_b=n\) in the definition of a good pair with \(n_a-n_b\leq n\) does not change the answer. From now on, we will call \((L,R)\) that satisfies \(n_a-n_b\leq n\) a good pair.

Then, if \((L,R)\) is a good pair with the maximum \(R-L\), it can be seen that \(L-1\) and \(R+1\) are multiples of \(a\). Therefore, we only need to consider the case where \(L=al+1,R=ar-1\).

Fix \(k\) and consider whether \(k=r-l\) can be achieved. Here, \(n_a = k-1\).

\(n_b\) can be calculated from the remainder when the smallest multiple of \(b\) greater than or equal to \(al+1\) is divided by \(a\). More specifically, if \(al+t\) is a multiple of \(b\) for \(1\leq t\leq b\), then \(n_b = \left\lfloor \frac{ak-1+b-t}{b}\right\rfloor\). From this, it can be seen that \(n_b = \left\lfloor \frac{ak-1+b-g}{b}\right\rfloor\) is the maximum value of \(n_b\) when \(k\) is fixed, where \(g = \gcd(a,b)\).

The condition for the existence of a good pair \((L,R)\) that satisfies \(k=r-l\) can be represented as:

\[(k-1)-\left\lfloor \frac{ak-1+b-g}{b}\right\rfloor\leq n.\]

From this, the maximum possible value of \(k\) (and thus the maximum possible value of \(R-L\)) can be calculated.

[2] Minimizing \(L\)

Considering the discussion in [1], the condition that \((L,R)=(al+1,ar-1)\) maximizes \(R-L\) can be expressed in the form that \(t\) is sufficiently small when the smallest multiple of \(b\) greater than or equal to \(al+1\) is \(al+t\). To find the minimum value of \(L\), we need to solve the following problem:

【Problem】

Given positive integers \(a,b,c\), find the smallest positive integer \(x\) such that \((ax\bmod b) \geq b - c\).

For such \(x\), if we appropriately set \(y=\lceil ax/b\rceil\), then \(\frac{a}{b}<\frac{y}{x}\). Here, it can be shown that \(\frac{y}{x}\) is the best upper approximation of \(\frac{a}{b}\). That is, for positive integers \(x',y'\), the following holds:

\[\frac{b}{a}<\frac{y'}{x'}\leq\frac{y}{x} \implies x\leq x'.\]

The best upper approximation of \(\frac{a}{b}\) can be enumerated in the form of \(O(\log b)\) linear equations by considering the Farey sequence or Stern-Brocot tree, so this problem can be solved in \(O(\log b)\) time.

• Related problem: https://judge.yosupo.jp/problem/min_of_mod_of_linear (Japanese editorial)

You can also solve this problem in \(O(\log^2 b)\) time using the floor_sum function of the AtCoder Library. This is because the existence of \(x\) such that \((ax\bmod b)\geq b-c\) can be determined by calculating \(\sum\left(\left\lfloor\frac{ax+c}{b}\right\rfloor-\left\lfloor\frac{ax}{b}\right\rfloor\right)\).