yukicoder contest 279 (Zelkova and Cherry)

　BCEの三完でした。

コンテストへのリンク

No.1358 [Zelkova 2nd Tune *] 語るなら枚数を...

　解説AC。

　制約を見ると、Y/max(N, K, H)で全探索してくれと言ってそう。

　あとは、$ax+by=c$という形の方程式の解の個数を求めれば良い。……のだけど、そこでコンテスト中は詰まってしまった。

　が、落ち着いて見ると、これは大学受験数学の典型。

　拡張ユークリッドの互除法で$ax_0+by_0=c$となる$(x_0, y_0)$を一つ求めて、$a(x-x_0)+b(y-y_0)=0$とすれば、$a(x-x_0)=b(y_0-y)=abk$とおくことで、x, yが0以上という条件をkの条件に言い換えられる。

　不定方程式の問題だと思えばできたはずなんだけど、何かで探索したい、という気持ちでいると気付かなくなってしまう……。良くないね。