ヒント → https://atcoder.jp/contests/arc166/editorial/7181

[1] \(R-L\) の最大化

\((L,R)\) が \(n_a-n_b\leq n\) を満たすならば \((L,R), (L,R+1), (L,R+2),\ldots\) のいずれかが \(n_a-n_b=n\) を満たします．したがって良い組の定義の条件 \(n_a-n_b=n\) を \(n_a-n_b\leq n\) に置き換えても答えは変化しません．そこで以下では \(n_a-n_b\leq n\) を満たす \((L,R)\) を良い組ということにします．

すると，\((L,R)\) が \(R-L\) が最大の良い組である場合，\(L-1\) および \(R+1\) は \(a\) の倍数であることが分かります．したがって，\(L=al+1,R=ar-1\) と書ける場合のみを考えればよいです．

\(k\) を固定して，\(k=r-l\) が達成できるかどうかを考えます．このとき \(n_a = k-1\) です．

\(n_b\) は \(al+1\) 以上の最小の \(b\) の倍数を \(a\) で割った余りから計算できます．より具体的には \(1\leq t\leq b\) に対して \(al+t\) が \(b\) の倍数であるとすると，\(n_b = \biggl\lfloor \dfrac{ak-1+b-t}{b}\biggr\rfloor\) です．このことから，\(g = \gcd(a,b)\) として \(n_b = \biggl\lfloor \dfrac{ak-1+b-g}{b}\biggr\rfloor\) が \(k\) を固定した場合の \(n_b\) の最大値であることが分かります．

\(k=r-l\) を満たす良い組 \((L,R)\) が存在するための条件は

\[(k-1)-\biggl\lfloor \dfrac{ak-1+b-g}{b}\biggr\rfloor\leq n\]

と表すことができて，ここから \(k\) としてありうる最大値（したがって \(R-L\) としてありうる最大値）が計算できます．

[2] \(L\) の最小化

[1] の議論を踏まえると，\((L,R)=(al+1,ar-1)\) が\(R-L\) を最大化するという条件は，\(al+1\) 以上の最小の \(b\) の倍数を \(al+t\) としたときに \(t\) が十分小さいという形で表すことができます．\(L\) の最小値を求めるためには次のような問題を解けばよいです：

【問題】

正整数 \(a,b,c\) が与えられる．\((ax\bmod b) \geq b - c\) を満たすような最小の正整数 \(x\) を求めよ．

このような \(x\) に対して適切に \(y=\lceil ax/b\rceil\) とすれば，\(\frac{a}{b}<\frac{y}{x}\) です．ここで，\(\frac{y}{x}\) が \(\frac{a}{b}\) の上側最良近似分数であることが示せます．つまり正整数 \(x',y'\) に対して

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

が成り立ちます．\(\frac{a}{b}\) の上側最良近似分数は Farey 数列 / Stern-Brocot tree を考えれば \(O(\log b)\) 個の 1 次式の形で列挙できて，この問題は \(O(\log b)\) 時間で解くことができます．

• 関連問題：https://judge.yosupo.jp/problem/min_of_mod_of_linear （日本語解説）

なお，AtCoder Library の floor_sum を用いて \(O(\log^2 b)\) 時間で解くこともできます．\((ax\bmod b)\geq b-c\) となる \(x\) の存在が，\(\sum\bigl(\bigl\lfloor\frac{ax+c}{b}\bigr\rfloor-\bigl\lfloor\frac{ax}{b}\bigr\rfloor\bigr)\) の計算により判定できるためです．