201051: [AtCoder]ARC105 B - MAX-=min

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

### 题目描述 你有一张编号为 $1$ 到 $N$ 的 $N$ 张牌。每张卡片上都有一个整数,第 $i$ 张卡片上写有数字 $a_i$ 。 苏努里先生将完成以下程序。 1. $X$ 表示拥有的卡片上写着的最大值, $x$ 表示最小值。 1. 当 $X = x$ 时结束程序。否则,将所有写有 $X$ 的卡片转换为写有 $X - x$ 的卡片,然后执行第1步。 程序最终保证会结束。结束后,输出你持有的卡片上写着的唯一的数字。 ### 输入格式 第一行输入一个整数 $N$ 。 接下来一行输入 $N$ 个整数 $a_i$ 。 ### 输出格式 输出你持有的卡片上写着的唯一的数字。 ### 说明/提示 #### 限制 $1 ≤ N ≤ 10^5$ $1 ≤ a_i ≤ 10^9$

加入题单

上一题 下一题 算法标签: