Codeforces 582A. GCD Table

問題

ある長さNの配列a_iがあったとき、この配列自体は与えられず、代わりにgcd(a_i,a_j)の結果N*N個が与えられる。
元の配列に含まれる数値を答える。

1<=N<=500
a_i<=10^9

考え方

与えられたgcd(a_i,a_j)の中で、一番大きい数をMとする。
gcd(M,M)=Mであるので、少なくとも、Mは1つは含まれる。
なので、gcd(a_i,a_j)からMを1つ取り除いておく。

次に、gcd(a_i,a_j)の中で一番大きい数をM2とする。
最初の配列にM2が含まれないとすると、他の要素でgcd取ったらM2になるものがあるはずだが、gcdの性質から、M2より大きい数値でないといけない。しかし、今の最大値はM2であるので、ありえない。
したがって、M2も含まれないといけない。なので、gcd(M2,M2)はのぞかれる。そして、これまで確定しているMに対して、gcd(M,M2)とgcd(M2,M)の分も確定するので、のぞいておく。

これを繰り返せば、矛盾なく、元の配列の要素を復元できる。