解答：Submission #20060874 - AtCoder Beginner Contest 191
解法：
「最終的に残る数」の構成
gcd(a, b) ≦ min(a, b) より、最終的に残る数はmin(A)以下である（以降min(A)をAminと呼ぶ）。また、あるAi1, Ai2, ..., Aixに対し、gcd(Ai1, Ai2, ..., Aix)はAmin以下であれば最終的に残る数の候補となりそうである。
実は最終的に残る数はAmin以下のgcd(Ai1, Ai2, ..., Aix)で構成される。X：最終的に残る数、Y：{gcd(Ai1, Ai2, ..., Aix), Amin以下}とし、X = Yであることを示す。
X⊂Yを示す。x∊Xに対し、A1, ..., ANの順列と、gcd or minの操作のN-1個の操作の選択が対応する。このときAisとAis+1に対し、gcdの操作が行われる場合はAisとAis+1をどちらも残し、minの操作が行われる場合は小さい方を残す作業を考える。この作業で最終的に残ったものにgcdの操作を行うと、その結果はxになり、かつx∊Yが言える。
Y⊂Xを示す。y∊Yに対し、以下の場合分けを考える。
なお、gcd(Ai1, Ai2, ..., Aix)は単項のgcdをgcd(Ai) = Aiとして定義する。本問で最終的に残る数はAmin以下であり、単項gcdとしてはAminしか採用されない。
gcd(Ai1, Ai2, ..., Aix)の全探索
gcd(Ai1, Ai2, ..., Aix)の全探索は愚直にやると指数時間のオーダーが必要となる。実は次のような効率のよいアルゴリズムが存在する。
- 各Aiの約数jに対し、変数tjを定義し、tj = Aiとする。既にtjが定義されている場合はtjをgcd(tj, Ai)に置き換える
- i = 1, 2, ..., Nに対し上記の操作を行い、最終的にtj = jとなっているものがgcd(Ai1, Ai2, ..., Aix)によってあらわされる数となる
X：上記アルゴリズムで生成される数の集合、Y：gcd(Ai1, Ai2, ..., Aix)の集合とし、X = Yを示す。
X⊂Yを示す。x∊Xとする。最初にtxが定義されるときのAの項をAiとすると、xはAiの約数である。このときx=Aiであれば、x=gcd(Ai)でありx∊Yである。x<Aiのときはxの定義より、Aiとは別の項のAj1, ..., Ajtが存在し、x = gcd(Ai, Aj1, ..., Ajt)となっているはずである。よってこの場合もx∊Yである。
Y⊂Xを示す。y∊Yとする。
- yがAの1つの項のAiのgcdであるとき
y = gcd(Ai) = Aiである。このとき、tAiに対する上記アルゴリズムの操作と、それに対するtAiの挙動を確認する。- Aiより前の項の操作
y | AgなるAgが存在したとすると、tAi = Agとして定義される。ただし、Ag以降にy | AhなるAhが1つでもあれば、tAi = gcd(Ag, Ah)となる。このとき、y' = gcd(Ag, Ah)とすると、gcdの性質よりy | y'である。 - Aiの操作
y | AgなるAgが存在したとき、tAiはy | y''なるy''を用いてtAi = y''と表せる。AiではtAi = gcd(y'', y) = yとなる。存在しなかったとき、tAi = yとして定義される。いずれの場合もtAi = yとなる。 - Aiより後の項の操作
y | AjなるAjではtAi = gcd(y, Aj) = yのままであるし、y | AjでないAjはtAiに影響を与えない。よって最終的にtAi = y = Aiとなる。
- Aiより前の項の操作
- yが複数の項のgcdであるとき
gcdに現れる項Aiに対してはy | y'なるy'が存在し、tAi = y'となる。また、gcdに現れる項の操作がすべて完了するとtAi = yとなる。gcdに現れない項Ajの操作については、y | AjであるAjではy | y'なるy'が存在し、tAj = y'となるし、y | AjでないAjはtAiに影響を与えない。よってこれも最終的にtAi = yとなる。
