分数: 400 分
问题陈述
Takahashi 正在观察由以下成分组成的培养物样本 N cells.
Each cell has an activity value represented by a positive integer.最初,活动值 i-th cell is A_i.
只要存在活动值为 在培养物样本中存在 2 或更多,Takahashi 重复执行以下步骤序列: 一次操作:
- Choose one cell from the culture sample whose activity value is 2 or more.让 x be the activity value of the chosen cell.
- Choose a prime number p that divides x.
- 从培养样品中取出该细胞,并添加 p 每个都有活性值的新细胞 x / p 培养样品。 (因为 p 是除数 x, x / p 是正整数。)
每次操作都会使单元格总数增加 p - 1。如果新添加的细胞的活性值为 2 或以上,他们就有资格在后续操作中被选择。细胞活性值为 无法选择 1 进行操作。
在每次操作中,高桥可以自由选择选择哪个单元格以及哪个素数 p to use.根据这些选择,直到所有单元格的活动值为 1 may vary.
找到 最小值 和 最大 使所有单元格的活动值等于所需的操作数 1.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^6
- 所有输入值均为整数。
输入
N A_1 A_2 \cdots A_N
第一行包含一个整数 N 代表单元格数量。
第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔。 坐标平面上的
输出
按此顺序在一行上打印所需操作的最小和最大数量,并用空格分隔。
示例输入 1
3 2 3 4
示例输出 1
5 5
示例输入 2
4 1 6 8 9
示例输出 2
14 15
示例输入 3
10 12 15 16 18 20 25 27 30 49 64
示例输出 3
141 171
示例输入 4
24 2 4 6 8 9 10 12 15 16 18 20 21 24 25 27 30 32 36 40 45 49 64 81 1000000
示例输出 4
250346 988666
示例输入 5
1 1
示例输出 5
0 0