1. paizaラーニングトップ
  2. レベルアップ問題集
  3. ユークリッドの互除法メニュー(言語選択)
  4. 問題一覧
  5. 3 つ以上の整数の最大公約数

ユークリッドの互除法メニューのサムネイル
3 つ以上の整数の最大公約数 (paizaランク C 相当)

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

問題

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

2 つの整数 A , B の最大公約数 (以後 gcd(A , B)) を高速に求めるアルゴリズムとして、ユークリッドの互除法があります。
gcd の演算では、3 つの整数 a, b, c の最大公約数は、gcd(gcd(a,b),c) で求めることができます。
これは 4 つ以上の整数の場合も同様に、a , b , c , d , e , ... の最大公約数は
gcd(...gcd(gcd(gcd(gcd(a,b),c),d),e)...) で求めることができます。

例として、(9,27,33) の最大公約数は gcd(gcd(9,27),33) = gcd(9,33) = 3 といった具合に求めることができます。

与えられる整数の数 N と、整数 A_1, ..., A_N が与えられるので、 A_1, ..., A_N の最大公約数を求めてください。

入力される値

N
A_1
...
A_N


・1 行目で、与えられる整数の個数 N が与えられます。
・続く N 行では、整数 A_i (1 ≦ i ≦ N) が先頭から順に与えられます。


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

gcd(A_1 , ... , A_N)


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

条件

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

入力例1

3
6
18
30

出力例1

6

入力例2

5
7
10
30
55
175

出力例2

1

問題一覧へ戻る

ページの先頭へ戻る