AtCoder Grand Contest 026 rng_10s

(A+kD)%B>Cまたは(A+kD)<B-Dを満たすkが存在しないかどうかで判定した。g=GCD(D,B)とすると、(A+kD)%BはgN+A%gの形の数(Nは任意の整数)を全部取ることに気付くと、O(1)で判定できる。