[AtCoder] ARC 105 B – MAX-=min

問題

方針

シミュレーション

カードの置き換えは全ての \( X \) に対して行われるので、セットを用います。セットは順序付きなので、最小値 \( x \) と最大値 \( X \) の取得を高速にできます。このとき、セットから \( X \) を消去します。ある操作で、\( X \bmod x = 0 \) であるとき、最大値 \( X \) を \( x \) とさせることができます。\( X \) に対して、操作 2. を連続して行っても、最小値は変化しないので、\( X \) を \( x \) にすることができます。\( X \bmod x \neq 0 \) であるとき、操作 2. を連続して行うと、\( X \) が  \( X \bmod x \) となったとき、最小値が \( x = X \bmod x \) と更新されるので、セットに \( X \bmod x \) を追加し、操作 2. を行います。

最大公約数

自然数 \( a \leq b\) の最大公約数を \( g(a, b) \) とすると、\( g(a, b) = g(a, b – a) \) が成り立ちます。したがって、配列 \( a \) の最大公約数が答えとなります。逆に、配列 \( a \) の最大公約数を \( b \) とすると、\( a_i \bmod b = 0 \) より、\( a_i = b \) とすることができます。

コード

シミュレーション

最大公約数