/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
黒板に N 個の整数 A_1, A_2, A_3, \dots, A_N が書かれています。
あなたは次の操作を N - 1 回行います。
- 黒板に書かれている数を 2 つ選んで消す。消した数を x と y として、\gcd(x, y) と \min(x, y) のどちらか一方を黒板に書く
N - 1 回の操作を終えた後、黒板にはただ一つの整数が残りますが、この整数として考えられるものはいくつありますか ?
制約
- 2 \le N \le 2000
- 1 \le A_i \le 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 A_3 \dots A_N
出力
黒板に残る整数として考えられるものの個数を出力せよ。
入力例 1
3 6 9 12
出力例 1
2
3 と 6 が、最後に黒板に残る整数として考えられるものです。
例えば以下のような操作をすることで 3 が残ります。
- 9 と 12 を選んで黒板から消し、\gcd(9, 12) = 3 を黒板に書く
- 6 と 3 を選んで黒板から消し、\min(6, 3) = 3 を黒板に書く
また、以下のような操作をすることで 6 が残ります。
- 6 と 12 を選んで黒板から消し、\gcd(6, 12) = 6 を黒板に書く
- 6 と 9 を選んで黒板から消し、\min(6, 9) = 6 を黒板に書く
入力例 2
4 8 2 12 6
出力例 2
1
2 が、黒板に残る数として考えられる唯一の数です。
入力例 3
7 30 28 33 49 27 37 48
出力例 3
7
1, 2, 3, 4, 6, 7, 27 が最後に黒板に残る整数として考えられるものです。
Score : 600 points
Problem Statement
There are N integers A_1, A_2, A_3, \dots, A_N written on a blackboard.
You will do the following operation N - 1 times:
- Choose two numbers written on the blackboard and erase them. Let x and y be the erased numbers. Then, write \gcd(x, y) or \min(x, y) on the blackboard.
After N - 1 operations, just one integer will remain on the blackboard. How many possible values of this number are there?
Constraints
- 2 \le N \le 2000
- 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 A_3 \dots A_N
Output
Print the number of possible values of the last remaining number on the blackboard.
Sample Input 1
3 6 9 12
Sample Output 1
2
The possible values of the last remaining number are 3 and 6.
We will have 3 in the end if, for example, we do as follows:
- choose 9, 12 and erase them from the blackboard, then write \gcd(9, 12) = 3;
- choose 6, 3 and erase them from the blackboard, then write \min(6, 3) = 3.
Also, we will have 6 in the end if, for example, we do as follows:
- choose 6, 12 and erase them from the blackboard, then write \gcd(6, 12) = 6;
- choose 6, 9 and erase them from the blackboard, then write \min(6, 9) = 6.
Sample Input 2
4 8 2 12 6
Sample Output 2
1
2 is the only number that can remain on the blackboard.
Sample Input 3
7 30 28 33 49 27 37 48
Sample Output 3
7
1, 2, 3, 4, 6, 7, and 27 can remain on the blackboard.