[AtCoder] ABC 180 D – Takahashi Unevolved

問題

方針

カコモンジムに通うことを操作1、AtCoder ジムに通うことを操作2とします。

\( i \) 回目の操作を行ったときの高橋君の強さを \( X_i \) とします。操作1を行うと、\( X_{i + 1} = AX_i \) となり、増分は

\[X_{i + 1} – X_{i} = (A – 1)X_i\]

となります。\( (A – 1)X_i > B \) のとき操作2を行った方が高橋君の強さは増えないことが分かります。したがって、\( (A – 1)X_i  \leq B \) を満たす限り、操作1を行い、残りは操作2を行います。

操作1を行った方が良い条件は、

\[ X_iA \leq Y – 1 \wedge (A – 1)X_i \leq B\]

なので、オーバーフローに注意する必要があります。128ビット整数を使うか、Python などの多倍長整数を気軽に扱える言語を使います。

コード