AGC 026 B - rng_10s

• 問題
• AC

とりあえず自明ケースを除いておく:

• $A < B$ならNo
• $B>D$ならNo
• 上記以外で$B \le C$ならYes

それ以外の場合では、Noになるのは在庫の数$X$が区間$(C, B)$に入ってしまう場合、つまり1回の購入量$B$より小さく補充の閾値$C$よりは大きい状態が発生してしまうケースである。これは$X$が$\mod B$で$C+1, C+2, ..., B-1$のいずれかと合同になる、と言い換えられる。

シミュレーションしながら考えてみる:

• 最初の在庫$A$が$\mod B$で$C+1, C+2, ..., B-1$のどれかと合同だとNo。
• $A \equiv 0, 1, ..., C \mod B$の場合は$D$個の補充に成功する。$A+D$が$\mod B$で$C+1, C+2, ..., B-1$のどれかと合同だとやはりNo。
• $A+D \equiv 0, 1, ..., C \mod B$の場合はさらに$D$個の補充に成功する。$A+2D$が$\mod B$で$C+1, C+2, ..., B-1$のどれかと合同だとやはりNo。
• …

というわけで、非負整数$x$が存在して$A+Dx$が$C+1, C+2, ..., B-1$のいずれかと合同の場合$(*)$はNo、それ以外はYesとわかる。

これで解けたと思ったのだが、そこから先のやり方がよくわかっていないことに気づいて考えこんでしまった……

合同方程式を解く方法に立ち戻る。$A+Dx \equiv d \mod B$を解くことは$Dx+By = d-A$を解くことと同じで、後者が可解であることは$d-A$が$\gcd(B, D)$の倍数であることと同値である。¹ したがって、条件$(*)$は$C+1-A, C+2-A, ..., B-1-A$の中に$\gcd(B,D)$の倍数が含まれる、と言い換えられる。これなら実装可能な判定方法になっている。つまり、$\gcd(B,D)$の倍数で$C+1-A$以上であるような最小のもの²を求めてそれが$B-A$未満ならNo、そうでなければYesである。

---

1. $x$が非負という条件は考える必要がない。整数解があれば必ず$x$が非負整数の解もあるため。 ↩︎

2. $y$以上の$x$の倍数で最小のものは、式としては$x \cdot \lceil y/x \rceil$と書ける。 ↩︎