問題文に書いたとおり、この問題は次の条件を満たす正整数 \(i\) を数える問題です。

• \(A + B\times i \leq x \leq A + C \times i\) を満たす \(D\) の倍数 \(x\) が存在しない。

まず、選べる区間の幅 \((A + C\times i) - (A + B \times i) = (C - B) \times i\) がある程度大きくなると、必ず \(D\) の倍数を含むようになります。

より厳密には、区間の幅が \(D - 1\) 以上になると、必ず \(D\) の倍数を含みます。よって、\(i \le \frac{D - 2}{C - B}\) としてよいです(また、これにより答えが有限なことが示せます)。

この問題の本質は、

• \(Y \leq x \leq Z\) を満たす \(D\) の倍数 \(x\) が存在しない
• \(\lfloor \frac{Y - 1}{D} \rfloor = \lfloor \frac{Z}{D} \rfloor\)

この2つの条件が同値であると気づくことです。更に、区間の幅が \(D - 1\) 未満ならば、\(\lfloor \frac{Z}{D} \rfloor - \lfloor \frac{Y - 1}{D} \rfloor\) は \(0\) か \(1\) になります。

よって、この問題で求めるものは、\(K = \lfloor \frac{D - 2}{C - B} \rfloor\) として

\[K - \sum_{i=1}^{K} (\lfloor \frac{A + C \times i}{D} \rfloor - \lfloor \frac{A + B \times i - 1}{D} \rfloor)\]

となります。

これはAC Libraryのfloor_sum を使用することで高速に計算できます。具体的な方法は、https://atcoder.jp/contests/practice2/tasks/practice2_c の解説を参照してください。