AtCoder Beginner Contest 191
翻译中…
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.
翻译中…
样例
Input #1
3
6 9 12
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$.
Input #2
4
8 2 12 6
Output #2
1
$2$ is the only number that can remain on the blackboard.
Input #3
7
30 28 33 49 27 37 48
Output #3
7
$1$, $2$, $3$, $4$, $6$, $7$, and $27$ can remain on the blackboard.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。