3 つ以上の整数の最大公約数 Erlang(Beta)編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
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) が先頭から順に与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
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
