Pythonのrangeオブジェクトと、二分探索を行う標準ライブラリであるbisectを用いる解法を紹介します。(bisectモジュールを知っていることを前提とします。)

まず、この問題を二分探索で解くことを考えます。\(A+kM\)と表されるような地点は無数にありますが、今回の問題では\(L,R\)が\(-{10}^{18}\)から\({10}^{18}\)であることから、この範囲の条件を満たす座標をすべて配列に昇順に記録します。

このとき答えは(この配列に含まれるR以下の個数) - (この配列に含まれるL未満の個数)と表すことができ、先ほど作った配列を\(X\)とすると bisect_right(X,R)-bisect_left(X,L) のように計算することができます。

上記の解法で問題となるのが配列\(X\)の要素数が最大で\(2 \times {10}^{18} + 1 \)個になってしまうことで、これを実際にlistなどで持つのは現実的ではありません。

ここで、Pythonのrangeオブジェクトを用います。Pythonのrangeオブジェクトは等差数列を管理するシーケンス型であり、ランダムアクセスが可能です。内部では開始地点と終了地点、ステップの値を持っているだけなので、大きな等差数列について大きなメモリ空間を使うことなく管理することができます。

また、Pythonのbisectモジュールは、len()でのサイズの取得ととランダムアクセスが可能ならば二分探索を行うことができます。

よって、配列\(X\)をrangeオブジェクトとして管理して、bisectモジュールで二分探索をすることで、この問題を解くことができます。

rangeオブジェクトのサイズを大きくしすぎる(\(2^{63}\)以上)とlen()を呼んだときにOverflowErrorが発生してしまいREとなってしまう点に注意してください。

実装例(Python)

from bisect import bisect_left,bisect_right
A,M,L,R = map(int,input().split())
X = range(A-(2*10**18)*M,10**18+1,M)
print(bisect_right(X,R) - bisect_left(X,L))