CodeChef Februrary Challenge - No Change Required

• 問題
• AC

整除性に関する列$D_1|D_2|...|D_N|P$が作れるとき、$P$を超えるコインを持っていれば必ずちょうど$P$が払える。

上の条件を満たさない場合の反例の作り方について。$P$を割り切らない$D_i$がある場合は自明な例が作れる。すべての$D_i$が$P$の約数である場合、$D_{i-1} \nmid D_i$となっている部分を見つける。このとき、$xD_i = P$を満たす$x$と$yD_{i-1} > D_i$を満たす最小の$y$について、コイン$i-1$を$y$枚、コイン$i$を$x-1$枚持てば、どのコインを減らしても$P$未満になる。

---

最初、すべてが$P$の約数ならNOと決めつけていて、$P=12$で4セント2枚と6セント1枚みたいな例に気づくのに長時間かかってしまった。