简答题 偏难
#17000

相等序列 时间限制:3.0 s 内存限制:512.0 MB 题目描述 小 A 有一个包含 N 个正整数的序列A = {A₁ , A₂ , · · ,A_N}。小…

相等序列
时间限制:3.0 s
内存限制:512.0 MB
题目描述

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

1. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i × P,P 为任意质数;
2. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i ÷ P,P 为任意质数,要求 A_i 能整除 P。
小 A 想请你帮他计算出令序列中所有整数都相同,最少需要花费多少金币。
输入格式
第一行一个正整数 N,含义如题面所示。
第二行包含 N 个正整数 A₁ , A₂ , · · ,A_N,代表序列 A。
输出格式
输出一行,代表最少需要花费的金币数量。
样例
输入样例

5
10  6  35  105  42

输出样例

8

数据范围
对于60%的测试点,保证 1 ≤ N, A_i ≤ 100。
对于所有测试点,保证 1 ≤ N, A_i ≤ 10⁵。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false;">tokens = [] def get_val() :     while not tokens:         tokens.extend(input().split())     return int(tokens.pop(0)) # 一共有多少数 n = get_val() # key:质数 # value:一个列表 ,num[p][exp]表示有多少数质因数分解后可以包含p^exp # 因为一个数最大就到10^5 ,相当于是10w ,所以列表最多包含20个数肯定够用 ,即2^20 num = {} for _ in range(n) :     # 统计一下各个输入数字有多少质因数     x = get_val()     d = 2     # 质因数必定小于根号x     tmp = x     while d * d &lt;= tmp:         # 如果找到了一个数是x的因数         if tmp % d == 0 :             cnt = 0             # 那就一直除以这个数 ,并且更新x的质因数数目             # 这样一来剩下能够整除x的必定是质数             while tmp % d == 0 :                 tmp //= d                 cnt += 1             if d not in num:                 num[d] = [0] * 20             # 数字x包含d^cnt ,更新状态             num[d][cnt] += 1         d += 1     # 如果x是质数     if tmp &gt; 1 :         if tmp not in num:             num[tmp] = [0] * 20         num[tmp][1] += 1 ans = 0 for p in num:     counts = num[p]     # 计算有多少数字不包含这个质因数     counts[0] = n - sum(counts)     # 寻找中位数指数     # 也就是寻找一个指数e,使得一半的数字包含超过e次方的p,另一半不包含     pos = 0     median_exponent = 0     for j in range(20) :         pos += counts[j]         if pos * 2 &gt;= n:             median_exponent = j             break     # 计算代价     for j in range(20) :         if counts[j] :             ans += counts[j] * abs(j - median_exponent) print(ans)</pre>
这道题暂未补解析。