分数: 300 点
问题陈述
给你一系列 N 正整数: A=(A_1,A_2,\dots,A_N).
您将重复以下操作,直到长度 A 变为 1.
- 让 k 的长度 A 在此操作之前。 选择整数 i 和 j 这样 \max(\{A_1,A_2,\dots,A_{k}\})=A_i,\min(\{A_1,A_2,\dots,A_{k}\})=A_j,和 i \neq j。 然后,更换 A_i 与 (A_i \bmod A_j)。 如果 A_i 变为 0 此时删除 A_i 来自 A.
查找您将执行的操作数。 我们可以证明,无论您如何选择 i,j 在操作中,操作总数没有变化。
约束
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
3 2 3 6
示例输出 1
3
您将执行 3 操作如下:
- 选择 i=3,j=1。你得到 A_3=0,然后删除 A_3 来自 A。现在你有 A=(2,3).
- 选择 i=2,j=1。你得到 A_2=1。现在你有 A=(2,1).
- 选择 i=1,j=2。你得到 A_1=0,然后删除 A_1 来自 A。现在你有 A=(1),并终止进程,因为长度 A 变为 1.
示例输入 2
6 1232 452 23491 34099 57341 21488
示例输出 2
12