← 返回题目列表

AtCoder · arc147_a

A. 最大模最小

中文机器翻译题面 查看原题

分数: 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