4214: Max Mod Min

# Max Mod Min ### 内存 1024MB ### 时间 2S ## 题目描述 小高得到了一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,...,A_N)$。 他将重复执行以下操作，直到序列 $A$ 的长度变为 $1$： - 设操作前 $A$ 的长度为 $k$。选择整数 $i$ 和 $j$，使得 $max({A_1,A_2,...,A_k})=A_i, min({A_1,A_2,...,A_k})=A_j$，且 $i≠j$。然后将 $A_i$ 替换为 $(A_i mod A_j)$。如果此时 $A_i$ 变为 $0$，则从 A 中删除 $A_i$。 请计算小高将执行的操作次数。可以证明，无论如何选择操作中的 $i$ 和 $j$，总操作次数都不会改变。 ## 输入格式 输入从标准输入中给出，格式如下： $N$ $A_1$ $A_2$ ... $A_N$ ## 输出格式 输出所求答案。 ## 输入输出样例 ### 输入样例1 ``` 3 2 3 6 ``` ### 输出样例1 ``` 3 ``` ### 输入样例2 ``` 6 1232 452 23491 34099 57341 21488 ``` ### 输出样例2 ``` 12 ``` ## 数据范围与提示 【样例1说明】 将执行3次操作，如下所示： 1. 选择 $i=3,j=1$。得到 $A_3=0$，并从 A 中删除 $A_3$。现在 $A=(2,3)$。 2. 选择 $i=2,j=1$。得到 $A_2=1$。现在 $A=(2,1)$。 3. 选择 $i=1,j=2$。得到 $A_1=0$，并从 A 中删除 $A_1$。现在 A=(1)，由于 A 的长度变为 1，终止操作。 【数据范围】 $2 ≤ N ≤ 2 × 10^5$ $1 ≤ A_i ≤ 10^9$ 所有输入均为整数。 ## 题目来源 ARC147A