最大公約数と最小公倍数 (paizaランク C 相当)

整数 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

というふうに求めることができます。