AGC026 B rng_10s
https://atcoder.jp/contests/agc026/tasks/agc026_b
愚直にシミュレーションをしていると間に合わないケースが多々あるので、与えられたパラメータから答えを導き出したくなります。
まずB<Dの時答えは明らかにNoになります。
毎日少しずつ在庫が減っていって増えることがないので。
次にA < Bの時も答えは明らかにNoになります。
初日に買えないので。
次にGCD(B, D)==1の場合について考えます。
この時、必ず在庫の数がC+1の状態でリンゴジュースをすぬけ君が買おうとする状況が発生します。
従ってC+1 >= Bを調べればよいです。
GCD(B, D)!=1の場合
すぬけ君来店後のリンゴジュースの在庫の取りうる値mは
m = A mod B + x * GCD(B, D)
になります。この時、m <= Cであればリンゴジュースが補充されるので、翌日すぬけ君はリンゴジュースを買うことができます。
したがってm > Cとなる最小のxの場合( x = x' )についてのみ考えれば良いです。
これはそのうちpdfで詳しく解説したいなあと思います。
