AtCoder AGC 026 B - rng_10s (青色, 600 点) - けんちょんの競プロ精進記録

あーーーーーー、これは大好物系なん！！！！！
本番でやってみたかったん！！！！！

問題へのリンク

問題概要 (AGC 026 B)

整数 $A, B, C, D$ があたえられる。
最初は在庫に $A$ 個あって、

毎日 $B$ 個ずつ消費される
その日の最後に $C$ 個以下しか残っていなかったら $D$ 個補充される

というのを繰り返す時、永遠に回せるかどうかを判定せよ (というクエリが $T$ 回与えられる)。

制約

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

考えたこと

とりあえず色んな状況があり得るのでちゃんと整理しないと...な感じなん。

$A$ < $B$ のときは自明に "No" (初期状態ですでにダメ)
$D$ < $B$ のときはジリ損するので "No" ( $C = ∞$ で毎ターン回復するとしてもいずれダメになる)

というのがすぐにわかり、以後 $A \ge B$ , $D \ge B$ としてよい。これで少し考えやすくなる。このとき、

f:id:drken1215:20180718032623j:plain

のような感じになる。

$C \ge B-1$ のときは黄色い部分が十分広くて受け止めてくれるので "Yes"

というのがまずは見て取れる。そしてこの構図を眺めていると、初期状態 $A$ からスタートして、結局は $D$ を足したり $B$ を引いたりしていることがわかる。そこで問題は

$p, q$ を $0$ 以上の整数として $Dp - Bq + A$ と表されるような整数の中に、上図の黄色いところをちょうど綺麗に飛び越えてしまうような値 (具体的には $C$ より大きくて $B$ 未満の数) が含まれていないか否か

を判定するような問題になる (厳密にはちゃんと示さないといけない)。
そして拡張 Euclid の互除法からの着想から、 $Dp - Bq + A$ で表される整数とはすなわち $G = {\rm GCD}(B, D)$ として、

$A + (G の倍数)$

と表されるような整数を動いていくことがわかる。したがって、 $A + (G の倍数)$ として表される数の中に、

$C$ より大きくて $B$ 未満の数が含まれていない: "Yes"
$C$ より大きくて $B$ 未満の数が含まれている: "No"

とすればよい。ところで、「 $A + (G の倍数)$ 」の $G$ の倍数の部分は負も含むことに注意。これは「 $G$ で割って $A$ % $G$ あまる数」と考えても同じになる。

#include <iostream>
using namespace std;

long long a, b, c, d;

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

bool solve() {
  if (a < b) return false;
  if (d < b) return false;
  if (c >= b-1) return true;

  long long g = GCD(b, d);

  // g で割って a%g あまる数で、c より大きく b 未満な整数があるかどうか
  // g で割って a%g あまる数で、b 未満の最大の数
  long long Max = (b - a%g + g-1)/g*g + a%g - g; // b が g の倍数であることを考慮して、Max = b + a%g - g でも OK
  if (Max > c) return false;
  else return true;
}

int main() {
  int T; cin >> T;
  for (int CASE = 0; CASE < T; ++CASE) {
    cin >> a >> b >> c >> d;
    if (solve()) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}