AGC026 B rng_10s - 足跡-sokuseki-

問題概要

はじめジュースの在庫が $A$ 本ある。
毎日 $B$ 本購入され、購入後 $C$ 本以下になると夜に $D$ 本補充する。
永遠にジュースを $B$ 本購入され続けるか。
クエリは $T$ 個。

制約

$T \le 300$
$1 \le A, B, C, D \le 10^{18}$

解法

まず、 $A < B$ の場合は、初日に $B$ 本購入できないので、必ず No になる。
また、そうでなくても、 $D < B$ の場合は、補充数が購入数に追いつかないのでいつか $B$ 本購入できなくなるので、 No になる。
逆に、上の2つを満たさない場合で $C \geq B-1$ の場合、常に補充が間に合うので永遠に $B$ 本購入でき、 Yes となる。

この3つの場合を除くと、残りは $A \geq B$ かつ $D \geq B$ かつ $C < B-1$ の場合である。

このときジュースを $B$ 本買えなくなるのは、前日購入後にジュースが $C$ 本より多くて補充されずに、かつ当日 $B$ 本未満だったときのみである。（ $D < B$ より補充されていないことがわかる）
つまり、ジュースの残数が $C+1$ 以上 $B-1$ 以下になってしまうと No となる。

$y$ 日後までに $x$ 回補充されたときにジュースの残数が $C+1$ 以上 $B-1$ 以下になったとすると
$C+1 \le A + Dx - By \le B-1$
が成り立つ。 mod $B$ をとると
$C+1 \le A + Dx \le B-1$
となる。
式変形すると、 mod $B$ において、 $Dx$ が [ $C+1-A$ , $B-1-A$ ]の範囲に含まれると No である。
mod $B$ において $Dx$ のとる値は gcd( $B$ , $D$ ) の倍数なので、mod $B$ において、gcd( $B$ , $D$ )が [ $C+1-A$ , $B-1-A$ ]の範囲に含まれると No であると言える。