← 返回题目列表

AtCoder · awc0045_d

D. 细胞分裂

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

Takahashi 正在观察由以下成分组成的培养物样本 N cells.

Each cell has an activity value represented by a positive integer.最初,活动值 i-th cell is A_i.

只要存在活动值为 在培养物样本中存在 2 或更多,Takahashi 重复执行以下步骤序列: 一次操作:

  1. Choose one cell from the culture sample whose activity value is 2 or more.让 x be the activity value of the chosen cell.
  2. Choose a prime number p that divides x.
  3. 从培养样品中取出该细胞,并添加 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