Codeforces 323, Division 1, A ( Division 2, C ) - GCD Table

問題文

　http://codeforces.com/contest/583/problem/C

問題概要

　$n$ 要素の数列 $a$ から生成されるGCD Table を，$$g_{ ij } = \mathrm{ gcd }( a_i, a_j )$$ なる $n \times n$ 行列とする．
　今，$g$ の要素を適当に並び替えた $n \times n$ 個の整数が与えられるので，$a$ として妥当なものを 1 つ復元せよ．解の存在は保証される．
　$1 \leq n \leq 500$

解法

　同じ値同士の GCD は元の値と同じなので，$g$ の元になった $a$ の要素は与えられる数値の中に全て含まれています．$a$ の要素は $g$ の対角要素に現れます．
　また，GCD をとったとき，結果は元の値の内大きくない方を超えません．従って，あるインデックス $i$ に着目すると，$g$ の $i$ 行と $i$ 列のそれぞれについて，$a_i$ より大きい要素は出現しません．
　これらのことを考慮すると，$a$ の要素を大きい方から 1 つずつ決めていくことができると分かります．以下の手順を繰り返します．

1. 未使用の整数の内，最大のものを選ぶ
2. 選んだ整数と，既に確定した $a$ の各要素との GCD を計算して，それらを使用済みにする（引数の順序で 2 個出てくるので 2 個ずつ消す）
3. 手順 1 で選んだ値を $a$ に加える

　正当性ですが，未確定の値の内最大のものが $a$ の要素でない（⇔ $g$ の対角要素でない）とすると先程の条件に反することから妥当であると言えます．
　実装するにあたり必要な操作は，

• 整数の多重集合から最大のものをとる（$O( n )$ 回発生）
• 集合から値を削除する（$O( n^2 )$ 回発生）

の 2 種類です．制約を考えるとてきとーにやっても大丈夫そうですが（未検証），std::multiset がこれらの機能を備えているので，そのまま使うのが楽です．
　std::multiset の操作が 1 回あたり $O( \log n )$ 時間なので，全体では $O( n^2 \log n )$ 時間となります．

コード

using VI = vector< int >;

template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }

#define FOR( e, c ) for ( auto &e : c )

#define PB push_back

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int N;
	cin >> N;

	multiset< int, greater< int > > G( istream_iterator< int >( cin ), ( istream_iterator< int >() ) );

	VI res;
	while ( !G.empty() )
	{
		const int g = *begin( G );
		G.erase( begin( G ) );

		FOR( a, res )
		{
			auto pos1 = G.find( __gcd( g, a ) ), pos2( pos1 );
			advance( pos2, 2 );
			G.erase( pos1, pos2 );
		}

		res.PB( g );
	}

	cout << res << endl;

	return 0;
}