素数メニューのサムネイル
最大公約数 (paizaランク C 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

複数個の整数に共通する約数のうち、最大のものを最大公約数といいます。
整数 N と N 個の整数 A_1 , ... , A_N が与えられるので、A_1 , ... , A_N の最大公約数を求めてください。
なお、最大公約数は、「全ての整数に共通する素因数の{最小の指数}乗」の積となることが知られています。
例として、12 , 30 , 81 の最大公約数は、 12 = 2^2 × 3^1 × 5^0 , 30 = 2^1 × 3^1 × 5^1 , 81 = 2^0 × 3^4 × 5^0 より、素因数 2 についての乗数の最小値は 0 , 素因数 3 についての乗数の最小値は 1 , 素因数 5 についての乗数の最小値は 0 であるため、最大公約数は 2^0 × 3^1 × 5^0 = 3 となります。

入力される値

N
A_1
...
A_N


・ 1 行目で整数 N が与えられます。
・ 続く N 行のうち、 i 行目では整数 A_i が与えられます。(1 ≦ i ≦ N)


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

・ A_1 , ... , A_N の最大公約数を 1 行で出力してください。
出力の末尾には改行を入れてください。

条件

・ 1 ≦ N ≦ 1,000
・ 1 ≦ A_i ≦ 100,000 (1 ≦ i ≦ N)

入力例1

2
6
8

出力例1

2

入力例2

4
7
14
35
60

出力例2

1

問題一覧へ戻る

ページの先頭へ戻る