简答题
偏难
#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。
输出格式
输出一行,代表最少需要花费的金币数量。
样例
输入样例
输出样例
数据范围
对于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 <= 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 > 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 >= n:
median_exponent = j
break
# 计算代价
for j in range(20) :
if counts[j] :
ans += counts[j] * abs(j - median_exponent)
print(ans)</pre>
这道题暂未补解析。