AGC 026 B - rng_10s
解法
- 明らかに,解説で除いている3ケースはわかる.
- そうでないとき, 個数をy個とすると無限に買い続けられるときは y = C の周りを振動する
- 無限ループするので,yが周期をもつ-> C+1 <= y <= C+B の値を全て取りうる? .. そうであればC+1-B>=0を判定すればOK
- 実際上のようなケースは gcd(B,D)=1のときに限られることがわかる
- ex. (A,B,C,D) = (7,3,1,6) は 7,4,1,7,4,1,..
- g = gcd(B,D) のとき A+kg であってCより大な最小のものがCより大きい最小な個数っぽい
- このようなkは k=(A-C-1)/g で求められるのでこれで A-kg-B>=0 であればOK
以上で1回のクエリがO(1)で解けた.
わざわざクエリ方式にしたのは嘘解法が無限に作れそうだからっぽい.
メモ
解けたが,解説のような綺麗な解法はできなかった.
以下のことを意識すると良いかも?
- 2回定数加算の操作があるときは1つのmodをとってみる(操作が1回になるため)
