题目背景

2025 年 12 月 GESP C++ 五级编程第 2 题

题目描述

小 A 有一个包含 $N$ 个正整数的序列 $A={A_1,A_2,ldots,A_N}$。每次可以花费 $1$ 个金币执行以下任意一种操作：

• 选择一个 $A_i$，将 $A_i$ 变为 $A_i imes P$，其中 $P$ 为任意质数；
• 选择一个 $A_i$，将 $A_i$ 变为 $A_i/P$，其中 $P$ 为任意质数，且要求 $A_i$ 能被 $P$ 整除。

请计算令序列中所有整数都相同，最少需要花费多少金币。

输入格式

第一行输入一个正整数 $N$。

第二行输入 $N$ 个正整数 $A_1,A_2,ldots,A_N$。

输出格式

输出一行一个整数，表示最少金币数。

5
10 6 35 105 42

8

数据范围与提示

• 对于 $60$ 的测试点，$1 \le N,A_i \le 100$
• 对于所有测试点，$1 \le N,A_i \le 10^5$

一次操作等价于让某个数的质因数分解中某个质数的指数增加或减少 $1$。可以分别考虑每个质数指数调整到同一值的最小代价。