問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
整数 N と N 個の整数 A_1, ..., A_N が与えられるので、A_1, ..., A_N の最大公約数と最小公倍数を求めてください。
最大公約数とは、複数個の整数に共通する約数のうち最大のものを指します。また、最小公倍数とは複数個の整数に共通する倍数のうち、最小のものを指します。
最大公約数と最小公倍数は、素数問題集 (https://paiza.jp/works/mondai/prime_number_primer/) で学んだ方法で解くこともできますし、今から説明するユークリッドの互除法を用いた方法でも解くことができます。
ある二つの数の最大公約数はユークリッドの互除法を用いて以下のような手順で求めることができます。
1. 一方が 0 なら終了
2. 小さい方で大きい方を割り、大きい方を余りで置き換える。
3. 1. が達成されるまで 2 を繰り返す。
4. 0 でない方の数が最大公約数である。
また、二つの数を A, B、最大公約数と最小公倍数をそれぞれ GCD, LCM とすると、これらの数には以下のような関係があります。A × B = GCD × LCM
これを用いると、最小公倍数はLCM = (A × B) / GCD
というふうに求めることができます。
・ 1 行目に整数 N が与えられます。
・ 2 行目以降に A_1, ..., A_N が N 行で与えられます。
N
A_1
...
A_N
整数 A_1, ..., A_N の最大公約数と最小公倍数を求め、最大公約数・最小公倍数の順に半角スペース区切りで出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 10
・ 1 ≦ A_i ≦ 100 (1 ≦ i ≦ N)
2
10
15
5 30
3
12
123
132
3 5412
5
12
45
78
96
63
3 131040