游游的数组询问
游游的数组询问
游游有一个长度为 n的数组，每个数的权值为它的质因子个数。现在游游想要删除一段长度刚好为 k 的子数组，删除后需要使剩下的数的权值和最大。问这个权值和是多少？
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
题目重述
游游有一个长度为n的数组，每个元素的权值是其质因子的个数。现在要删除一个长度恰好为k的子数组（连续的k个元素），使得剩下的元素的权值和最大。求这个最大的权值和。
示例分析
输入：
5 2
6 2 4 1 3输出：
4解释：
- 计算每个元素的权值（质因子个数）：
- 6：质因子2和3 → 权值2
- 2：质因子2 → 权值1
- 4：质因子2 → 权值1
- 1：无质因子 → 权值0
- 3：质因子3 → 权值1
- 删除子数组[4,1]（权值和为1+0=1），剩下的[6,2,3]权值和为2+1+1=4
解题思路
预处理质因子个数：使用筛法预处理1到10000（因为a_i ≤ 10^4）的质因子个数，存储每个数的不同质因子个数。
计算权值数组：根据预处理结果，计算每个元素的权值，形成权值数组w。
滑动窗口求最小权值和子数组：
- 问题转化为：在权值数组w中，找到一个长度为k的子数组，其权值和最小（因为删除权值和最小的子数组，剩下的权值和最大）。
- 使用滑动窗口技术，计算所有长度为k的子数组的和，并记录最小值。
计算最终结果：
- 总权值和减去最小子数组和即为答案。
关键步骤详解
预处理质因子个数：
- 使用埃拉托斯特尼筛法（筛法）预处理每个数的最小质因子（Smallest Prime Factor, SPF）。
- 对于每个数，分解质因子并统计不同质因子的个数。
计算权值数组：
- 对于数组中的每个元素，查询其质因子个数，得到权值数组w。
滑动窗口求最小子数组和：
- 初始化窗口和为前k个元素的和。
- 滑动窗口，每次移动一个元素，更新窗口和，并记录最小值。
计算最终结果：
- 总权值和为权值数组w的所有元素之和。
- 最大剩余权值和 = 总权值和 - 最小子数组和。
解决代码
import sysdef precompute_prime_factors(max_num):# 筛法预处理每个数的最小质因子spf = [0] * (max_num + 1) #创建一个长度为 max_num + 1 的数组，初始化为0spf[0], spf[1] = 0, 1 # 特殊处理0和1（0没有质因数，1的质因数定义为1）for i in range(2, max_num + 1): #从2开始遍历每个数字if spf[i] == 0: #如果 spf[i] 仍然是0，说明 i 是质数（因为还没有比它小的数标记过它）spf[i] = i #将质数 i 的最小质因数设为它自己# 对于每个质数 i，从 i*i 开始标记它的所有倍数for j in range(i * i, max_num + 1, i):#如果某个数 j 还没有被标记过最小质因数（spf[j] == 0），则 i 就是它的最小质因数if spf[j] == 0: spf[j] = i# 计算每个数的不同质因子个数factor_count = [0] * (max_num + 1)for num in range(2, max_num + 1):x = numfactors = set()while x != 1:factors.add(spf[x])x = x // spf[x]factor_count[num] = len(factors)return factor_countdef solve():input = sys.stdin.read().split()ptr = 0n, k = map(int, input[ptr:ptr + 2])ptr += 2a = list(map(int, input[ptr:ptr + n]))ptr += nif n == 0:print(0)returnmax_a = max(a)factor_count = precompute_prime_factors(max_a)w = []for num in a:if num == 1:w.append(0)else:w.append(factor_count[num])total = sum(w)if k == 0:print(total)return# 滑动窗口找长度为k的最小和子数组min_sum = float('inf')current_sum = 0left = 0for right in range(n):current_sum += w[right]if right >= k - 1:if current_sum < min_sum:min_sum = current_sumcurrent_sum -= w[left]left += 1print(total - min_sum)if __name__ == "__main__":solve()复杂度分析
- 预处理质因子个数：O(M log log M)，其中M是最大的a_i（这里是10^4）。
- 计算权值数组：O(n)，遍历数组一次。
- 滑动窗口求最小子数组和：O(n)，每个元素被处理两次（加入和移除窗口）。
- 总复杂度：O(M log log M + n)，对于n ≤ 10^5和M=10^4是完全可行的。
示例验证
输入：
5 2
6 2 4 1 3处理过程：
- 预处理1到6的质因子个数：
- 1: 0
- 2: 1
- 3: 1
- 4: 1
- 5: 1
- 6: 2
- 权值数组w：[2, 1, 1, 0, 1]
- 总权值和：2 + 1 + 1 + 0 + 1 = 5
- 滑动窗口找长度为2的最小和子数组：
- [2,1]：和=3
- [1,1]：和=2
- [1,0]：和=1（最小值）
- [0,1]：和=1
- 最大剩余权值和：5 - 1 = 4
输出：
4为什么从从 i*i 开始标记倍数？
在生成最小质因数（SPF）表时，从 i*i 开始标记倍数，而不是从 2*i 开始，这是为了避免重复标记，提高算法效率。具体原因如下：
1. 为什么不是从 2*i 开始？
如果从 2*i 开始标记，例如 i = 5 时，你会标记：
5 * 2 = 10（最小质因数是2，但spf[10]已经被i=2时标记为2）5 * 3 = 15（最小质因数是3，但spf[15]已经被i=3时标记为3）5 * 4 = 20（最小质因数是2，已经被i=2标记）5 * 5 = 25（这才是i=5需要处理的最小未标记数）
问题：10, 15, 20 的最小质因数已经被更小的质数（2或3）标记过了，再让 i=5 去检查它们就是重复工作。
2. 为什么从 i*i 开始？
从 i*i 开始，可以确保：
- 所有比
i*i小的合数，都已经被比i更小的质数标记过了。 - 只有
i*i及更大的倍数才可能以i为最小质因数。
例子（i=5）：
5 * 5 = 25（最小质因数是5，之前未被标记）5 * 6 = 30（最小质因数是2，但spf[30]已经被i=2标记为2，所以i=5不会真正标记它）5 * 7 = 35（最小质因数是5，因为7 > 5，且35之前未被标记）
关键点：
- 如果
j = k*i（k < i），那么j的最小质因数一定 ≤k（因为k可能是合数，但它的质因数一定比i小）。 - 因此，
i只需要从i*i开始标记，因为更小的倍数已经被更小的质数处理过了。
3. 数学证明
假设 j = k*i，其中 k < i：
- 如果
k是质数，那么spf[j]已经被k标记过了（因为k < i）。 - 如果
k是合数，那么k的最小质因数p ≤ k < i，所以spf[j]已经被p标记过了。
因此，i 只需要从 i*i 开始标记，因为更小的 j = k*i 已经被更小的质数处理了。
4. 对比埃拉托斯特尼筛法（普通筛法）
- 普通筛法：从
2*i开始标记，因为它只需要知道某个数是否是合数，不关心最小质因数。 - SPF筛法：从
i*i开始，因为要确保spf[j]只被最小的质因数标记。
5. 例子分析
以 max_num = 30 为例，i=5 时的标记过程：
- 从
5 * 5 = 25开始：spf[25] = 5（因为之前未被标记） - 下一个
5 * 6 = 30：spf[30]已经被i=2标记为2，所以跳过。
如果从 2 * 5=10 开始：
spf[10]已经是2（正确，因为2 < 5），不需要i=5处理。spf[15]已经是3（正确，因为3 < 5），不需要i=5处理。spf[20]已经是2（正确，因为2 < 5），不需要i=5处理。
总结
从 i*i 开始是为了：
- 避免重复标记：确保
spf[j]只被最小的质因数标记。 - 提高效率：减少不必要的操作，让算法更高效。
- 正确性保证：数学上可以证明，所有比
i*i小的合数都已经被更小的质数处理过了。