Codeforces #323 Div. 2 C GCD Table
問題
方針
最初は $a$ を空にして順々に追加していく方針で解く. 残っている整数を multiset などで管理しながら,テーブルの確定する正方形の部分を広げていく. 最初に multiset 中で最大のものを $x$ とすると $\gcd(x,x)=x$ 以外にそれを作れる 2 つの整数は無いので, $a$ に $x$ を追加する.$x$ を使ったので multiset から除く. 次に大きい整数 $y$ も同様に $a$ に追加する. すると $x$ と $y$ の行と列が交わる部分の 2 マスに入るべき整数が確定するので,それも multiset から除く. これを $a$ の長さが $n$ になるまで続ける.
std::multiset
で 1 つだけ消す方法を知らなかったので下の実装では std::map
を使ってひどいことをしている.
multiset
で 1 つだけ消すにはイテレータを渡すといいらしい.
実装
int n;
vector<int> a;
#define ERASE(m,e) \
do { \
m[e]--; \
if(m[e]==0) m.erase(e); \
} while(0) \
void show(map<int,int> m){
vector<int> a;
for(auto & e : m){
rep(i,e.second) a.push_back(e.first);
}
dump(a);
}
vector<int> solve(){
vvi tab(n,vi(n,-1));
vector<int> idx(n);
int size = 0;
map<int,int> m;
rep(i,a.size()) m[a[i]]++;
while(size < n){
int t = m.rbegin()->first;
ERASE(m,t);
idx[size] = t;
tab[size][size] = t;
size++;
rep(i,size)rep(j,size){
if(tab[i][j] != -1) continue;
int g = __gcd(idx[i], idx[j]);
tab[i][j] = g;
ERASE(m,g);
}
dump(idx);
for(auto & e : m){
dump(e);
}
}
return idx;
}
signed main(){
while(cin >> n){
a.resize(n*n);
rep(i,n*n) cin >> a[i];
cout << solve() << endl;
}
}