#MX179. 数学家猫猫

数学家猫猫

时间限制:1000ms

空间限制:512MB

题目描述

猫猫最近在学习数学,它在黑板上写下了 NN 个正整数:A_1,A_2,…,A_NA\_1, A\_2, \dots, A\_N。为了训练自己的数学思维,它开始进行一项操作游戏。

这个游戏的规则如下:猫猫每次选择黑板上任意两个数,把它们擦掉,并写下它们的 gcd⁡\gcd(最大公约数)或者 min⁡\min(较小值)。这个过程一共重复 N−1N - 1 次,直到黑板上只剩下一个数。

猫猫很好奇,在所有可能的操作顺序以及选择 gcd⁡\gcd 或 min⁡\min 的情况下,最后可能留下多少种不同的整数结果?

请你帮助猫猫计算留下的不同整数结果数量。

输入格式

N
A_1 A_2 ... A_N
  • 第一行包含一个整数 NN,表示初始在黑板上的数字个数。
  • 第二行包含 NN 个整数 A_iA\_i,表示这些数字的初始值。

输出格式

输出一个整数,表示最后剩下的数字可能的不同取值个数。

样例 1 输入

3
6 9 12

样例 1 输出

2

样例解释 1

可能的最终结果有两种:33 和 66。例如:

  • 操作顺序一:99 和 1212 得到 gcd⁡(9,12)=3\gcd(9,12)=3,再用 66 和 33 得到 min⁡(6,3)=3\min(6,3)=3。
  • 操作顺序二:66 和 1212 得到 gcd⁡(6,12)=6\gcd(6,12)=6,再用 66 和 99 得到 min⁡(6,9)=6\min(6,9)=6。

样例 2 输入

7
30 28 33 49 27 37 48

样例 2 输出

7

样例解释 2

最终可能剩下的数字包括:11,22,33,44,66,77 和 2727,共 77 种结果。

样例 3 输入

4
8 2 12 6

样例 3 输出

1

数据规模与约定

  • 2≤N≤20002 \leq N \leq 2000
  • 1≤A_i≤1091 \leq A\_i \leq 10^9
测试点编号 数据范围
1∼31\sim3 1≤n≤2000,0≤ai≤20001 \leq n \leq 2000,0 \leq a_{i} \leq 2000
4∼64\sim6 1≤n≤2000,0≤ai≤1051 \leq n \leq 2000,0 \le a_{i} \leq 10^{5} ,不保证数据随机
7∼107\sim10 1≤n≤2000,0≤ai≤1091 \leq n \leq 2000,0 \le a_{i} \leq 10^9 ,不保证数据随机