/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、N 個の細胞からなる培養サンプルを観察している。
各細胞には正の整数で表される活性値がある。はじめ、i 番目の細胞の活性値は A_i である。
高橋君は、培養サンプル中に活性値が 2 以上の細胞が存在する限り、以下の一連の手順を 1 回の操作 として繰り返し行う。
- 培養サンプル中の活性値が 2 以上の細胞を 1 つ選ぶ。選んだ細胞の活性値を x とする。
- x を割り切る素数 p を 1 つ選ぶ。
- その細胞を培養サンプルから取り除き、代わりに活性値 x / p の細胞を p 個培養サンプルに加える。（p は x の約数であるため x / p は正の整数である。）
1 回の操作で細胞の総数は p - 1 個増える。新たに加えられた細胞の活性値が 2 以上であれば、以降の操作で選ぶ対象となる。活性値が 1 の細胞は操作の対象にならない。
各操作において、どの細胞を選ぶか、またどの素数 p を選ぶかは自由に決めることができる。これらの選び方によって、すべての細胞の活性値が 1 になるまでの操作回数は変わりうる。
すべての細胞の活性値を 1 にするために必要な操作回数の 最小値 と 最大値 を求めよ。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^6
- 入力はすべて整数である。
入力
N A_1 A_2 \cdots A_N
1 行目には、細胞の個数を表す整数 N が与えられる。
2 行目には、N 個の整数 A_1, A_2, \ldots, A_N が空白区切りで与えられる。
出力
必要な操作回数の最小値と最大値をこの順に、スペース区切りで 1 行に出力せよ。
入力例 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
Score : 400 pts
Problem Statement
Takahashi is observing a culture sample consisting of N cells.
Each cell has an activity value represented by a positive integer. Initially, the activity value of the i-th cell is A_i.
As long as there exists a cell with an activity value of 2 or more in the culture sample, Takahashi repeatedly performs the following sequence of steps as one operation:
- Choose one cell from the culture sample whose activity value is 2 or more. Let x be the activity value of the chosen cell.
- Choose a prime number p that divides x.
- Remove that cell from the culture sample, and add p new cells each with activity value x / p to the culture sample. (Since p is a divisor of x, x / p is a positive integer.)
Each operation increases the total number of cells by p - 1. If the activity value of the newly added cells is 2 or more, they become eligible to be chosen in subsequent operations. Cells with an activity value of 1 cannot be chosen for operations.
In each operation, Takahashi is free to choose which cell to select and which prime number p to use. Depending on these choices, the number of operations required until all cells have an activity value of 1 may vary.
Find the minimum and maximum number of operations required to make the activity values of all cells equal to 1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^6
- All input values are integers.
Input
N A_1 A_2 \cdots A_N
The first line contains an integer N representing the number of cells.
The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces.
Output
Print the minimum and maximum number of required operations in this order, separated by a space, on a single line.
Sample Input 1
3 2 3 4
Sample Output 1
5 5
Sample Input 2
4 1 6 8 9
Sample Output 2
14 15
Sample Input 3
10 12 15 16 18 20 25 27 30 49 64
Sample Output 3
141 171
Sample Input 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
Sample Output 4
250346 988666
Sample Input 5
1 1
Sample Output 5
0 0