N 個の正の整数 a_1, a_2, ..., a_N が与えられます。これら N 個すべての最大公約数（GCD）と最小公倍数（LCM）を求めてください。
入力は以下の形式で標準入力から与えられます。1 行目に個数 N、2 行目に N 個の整数が空白区切りで並びます。
N a_1 a_2 ... a_N
最大公約数と最小公倍数を、この順に半角スペースで区切って 1 行に出力してください。
GCD LCM
| 入力 | 出力 |
|---|---|
2 12 18 | 6 36 |
3 4 6 8 | 2 24 |
2 つの数の最大公約数を求めるユークリッドの互除法が主役です。基本情報でも頻出なので、ぜひ手に入れておきましょう。
a / GCD(a, b) * b で求まります。先に割ってから掛けると、桁あふれ（オーバーフロー）を防げます。大きな数を扱うので、変数は long long（Java は long）にしておくと安心です。互除法は一度書けると一生モノのテクニックですよ。
下のエディタにコードを書き、「コンパイル・実行」で試し、「提出」で全テスト採点します。言語は C / C++ / Java から選べます。全テスト合格でこの問題はクリア（👑）です。
本番の編集・コンパイル・実行・採点は Exercode 上で行います。このページは予習・練習用です（実行は Wandbox の実コンパイラを利用）。