ARC111 E - Simple Math 3 (800)
コンテスト中の考察
$ (A+Ci)-(A+Bi) \le D - 2つまり$ i \le \frac{D-2}{C-B}である必要がある
iが1大きくなる毎に区間の左辺は$ D-B、右辺は$ D-C左に移動する
条件を満たすには$ \lfloor \frac{A+Bi}{D} \rfloor = \lfloor \frac{A+Ci}{D} \rfloor である必要がある
実際には$ \lfloor \frac{A+Bi-1}{D} \rfloor = \lfloor \frac{A+Ci}{D} \rfloor
$ A+BiがDの倍数の時に元の式だと駄目
これを満たすかどうかを考えるのに結局$ O(D)で全体で$ O(TD)で間に合わない
解説の方法
上の式を高速に求めるfloor_sum()がACLには存在する
$ \lfloor \frac{A+Ci}{D} \rfloor - \lfloor \frac{A+Bi-1}{D} \rfloor が1なら間にDの倍数があり、0なら存在しないことが分かる
2回floor_sum()を使うことで$ O(\log D)ほどで計算できる
ここで計算できるのはDの倍数が含まれる区間となる$ iの数なので、答えはこれを区間の数から引いたものになる
$ O(T \log D)程度になるので間に合う