B - MAX-=min Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

すぬけ君は 1 から N の番号がついた N 枚のカードを持っています。 それぞれのカードには整数が書かれており、カード i には a_i が書かれています。

すぬけ君は以下の手続きを行います。

  1. すぬけ君が持っているカードに書かれた数の最大値を X、最小値を x とする。
  2. X = x なら手続きを終了する。そうでなければ X が書かれたカードを全て X-x が書かれたカードに変え、1 へ戻る。

この問題の制約下で、いずれ手続きが終了することが証明できます。手続き終了後のすぬけ君が持っているカードに書かれた唯一の数を求めてください。

制約

  • 与えられる入力は全て整数
  • 1 \leq N \leq 10^{5}
  • 1 \leq a_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 \cdots a_N

出力

手続き終了後のすぬけ君が持っているカードに書かれた唯一の数を出力せよ。

入力例 1

3
2 6 6

出力例 1

2
  • 手続き開始時点では、すぬけ君が持っているカードに書かれた数は (2,6,6) です。
    • x=2,X=6 なので、6 と書かれたカードを全て 4 が書かれたカードに書き換えます。
  • すぬけ君が持っているカードに書かれた数は (2,4,4) になっています。
    • x=2,X=4 なので、4 と書かれたカードを全て 2 が書かれたカードに書き換えます。
  • すぬけ君が持っているカードに書かれた数は (2,2,2) になっています。
    • x=2,X=2 なので手続きを終了します。

入力例 2

15
546 3192 1932 630 2100 4116 3906 3234 1302 1806 3528 3780 252 1008 588

出力例 2

42

Score : 300 points

Problem Statement

Snuke had N cards numbered 1 through N. Each card has an integer written on it; written on Card i is a_i.

Snuke did the following procedure:

  1. Let X and x be the maximum and minimum values written on Snuke's cards, respectively.
  2. If X = x, terminate the procedure. Otherwise, replace each card on which X is written with a card on which X-x is written, then go back to step 1.

Under the constraints in this problem, it can be proved that the procedure will eventually terminate. Find the number written on all of Snuke's cards after the procedure.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 10^{5}
  • 1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \cdots a_N

Output

Print the number written on all of Snuke's cards after the procedure.

Sample Input 1

3
2 6 6

Sample Output 1

2
  • At the beginning of the procedure, the numbers written on Snuke's cards are (2,6,6).
    • Since x=2 and X=6, he replaces each card on which 6 is written with a card on which 4 is written.
  • Now, the numbers written on Snuke's cards are (2,4,4).
    • Since x=2 and X=4, he replaces each card on which 4 is written with a card on which 2 is written.
  • Now, the numbers written on Snuke's cards are (2,2,2).
    • Since x=2 and X=2, he terminates the procedure.

Sample Input 2

15
546 3192 1932 630 2100 4116 3906 3234 1302 1806 3528 3780 252 1008 588

Sample Output 2

42