けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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;
  }
}