A - Max Mod Min
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
あなたは以下の操作を A の長さが 1 になるまで繰り返します。
- 操作を行う時点での A の長さを k とする。\max(\{A_1,A_2,\dots,A_{k}\})=A_i,\min(\{A_1,A_2,\dots,A_{k}\})=A_j かつ i \neq j を満たす整数の組 (i,j) を選び、A_i を (A_i \bmod A_j) で置き換える。このとき、A_i=0 となったのであれば A から A_i を削除する。
どのように操作を行っても操作回数は一定であることが証明できます。操作回数を求めてください。
制約
- 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 から A_3 を削除する。A=(2,3) となる。
- i=2,j=1 を選ぶ。A_2=1 となる。A=(2,1) となる。
- i=1,j=2 を選ぶ。A_1=0 となるため、A から A_1 を削除する。A=(1) となる。A の長さが 1 になったため、操作を終了する。
入力例 2
6 1232 452 23491 34099 57341 21488
出力例 2
12
Score : 300 points
Problem Statement
You are given a sequence of N positive integers: A=(A_1,A_2,\dots,A_N).
You will repeat the following operation until the length of A becomes 1.
- Let k be the length of A before this operation. Choose integers i and j such that \max(\{A_1,A_2,\dots,A_{k}\})=A_i,\min(\{A_1,A_2,\dots,A_{k}\})=A_j, and i \neq j. Then, replace A_i with (A_i \bmod A_j). If A_i becomes 0 at this moment, delete A_i from A.
Find the number of operations that you will perform. We can prove that, no matter how you choose i,j in the operations, the total number of operations does not change.
Constraints
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 2 3 6
Sample Output 1
3
You will perform 3 operations as follows:
- Choose i=3,j=1. You get A_3=0, and delete A_3 from A. Now you have A=(2,3).
- Choose i=2,j=1. You get A_2=1. Now you have A=(2,1).
- Choose i=1,j=2. You get A_1=0, and delete A_1 from A. Now you have A=(1), and terminate the process because the length of A becomes 1.
Sample Input 2
6 1232 452 23491 34099 57341 21488
Sample Output 2
12