区間の左端のみに注目すればよいので、 「\( L \le (ax+b)\%M \le R\) をみたす非負整数 \(x\) の最小値を計算せよ」という問題が解ければよいです。 この問題は以下の通り対数時間で解けます。

集合 \(S\), 関数 \(g\) を以下で定めます。求める値は \( g(L-b,R-b,a,M)\) です。

• \( S = S(L,R,a,M) = \{(x,y) \in \mathbb{Z}^2 \mid L \le ax-My \le R )\} \)
• \( g(L,R,a,M)\) を、\( (x,y) \in S,\, x \ge 0\) をみたす \(x\) の最小値とする

\(g\) は次の手順で再帰的に計算できます。

• \(L\) と \(R\) の間に \(M\) の倍数が存在するとき \( g(L,R,a,M) = 0\)
• そうでないとき \( g(L,R,a,M) = g(L\%M,R\%M,a,M)\) なので右辺を計算する
• （以下 \(0 \le L \le R < M\)）
• \(S\) における \(y \ge 0\) の最小値を\( y_0\)とおくと \( g(L,R,a,M) = \lceil (L+My_0)/a \rceil\) となる
  • \( 0 \le L \le R < M, \,0 < a < M\) のとき、 \(y\) の非負最小値をとる \(S\) の元は \(x\) の非負最小値もとる（これは非自明です）ことからしたがう
• \(y_0\) の定義により \( y_0 = g(L,R,-M,-a)\) であり、これは \( g(L,R,(-M)\%a,a)\) と等しいので、再帰的に \(y_0\) が計算できる

ただしこの再帰では再帰回数が多いです。そこで \(2a > M\) なら \(g(L,R,a,M) = g(-R,-L,M-a,M)\) を呼び出すことにすると、再帰\(2\)回ごとに \(M\) が半分になるので対数時間で処理できます。

https://atcoder.jp/contests/abc193/submissions/20627132