思路

这个问题可以分解为两个主要步骤：

1. 高效计算每个数字的重量。
2. 在计算出的重量序列上，寻找长度不超过 $k$ 的最大连续子段和。

第一步：计算每个数字的重量

一个数字 $x$ 的重量是其质因数分解中最大的指数。要计算它，我们首先需要对 $x$ 进行质因数分解。

• 朴素方法：对每个数字 $a_i$ 进行试除法，从 $2$ 开始到 $\sqrt{a_i}$ 来寻找质因子。对于单个数字 $a_i \approx 10^7$，这个方法是可行的。但由于测试数据组数 $T$ 和序列长度 $n$ 的总和可能很大（最多 $2 \times 10^5$），对每个数字都这样做会导致超时。

• 优化方法：线性筛预处理 为了加速质因数分解，我们可以预先计算出 $2$ 到 $10^7$ 范围内每个数的最小质因子 (Smallest Prime Factor, SPF)。这可以通过类似于埃氏筛或线性筛的方法在 $O(V \log \log V)$ 或 $O(V)$ 的时间内完成，其中 $V$ 是 $a_i$ 的最大值（$10^7$）。

  预处理步骤 (Sieve):

  1. 创建一个数组 spf，大小为 MAX_A ($10^7+1$)。
  2. 初始化 spf[i] = i。
  3. 遍历从 $2$ 到 $\sqrt{\text{MAX\_A}}$ 的数 i。如果 spf[i] == i，说明 i 是一个质数。
  4. 对于这个质数 i，遍历它的倍数 j = i*i, i*i+i, ...。如果 j 的最小质因子尚未被标记（即 spf[j] == j），则将其标记为 i（spf[j] = i）。

  计算重量步骤: 有了 spf 数组，分解任何数 $x$ 就变得非常快。

  1. 当 $x > 1$ 时，不断用 $p = \text{spf}[x]$ 去除 $x$，并计数。
  2. 例如，对于 $x = 90$，$\text{spf}[90]=2$。我们用 $2$ 去除 $90$，得到 $45$，指数为 $1$。现在 $x=45$。
  3. $\text{spf}[45]=3$。我们用 $3$ 去除 $45$，得到 $15$，再除得到 $5$，指数为 $2$。现在 $x=5$。
  4. $\text{spf}[5]=5$。我们用 $5$ 去除 $5$，得到 $1$，指数为 $1$。现在 $x=1$，分解结束。
  5. 记录过程中出现的最大指数即为 $x$ 的重量。 这个分解过程的时间复杂度约为 $O(\log x)$。由于所有测试用例的 $n$ 的总和有限，这个方法是足够高效的。

第二步：求解长度不超过 k 的最大连续子段和

在第一步之后，我们得到了一个由每个 $a_i$ 的重量组成的新的序列 $w_1, w_2, \ldots, w_n$。问题转化为：在这个 $w$ 序列上，找到一个长度不超过 $k$ 的连续子段，使其和最大。

这是一个经典的滑动窗口问题。我们可以使用前缀和与单调队列来解决。

1. 前缀和： 首先，计算重量序列 $w$ 的前缀和数组 $P$。定义 $P[i] = \sum_{j=1}^{i} w_j$，并且 $P[0] = 0$。 那么，子段 $w_j, \ldots, w_i$ 的和就可以表示为 $P[i] - P[j-1]$。

2. 问题转化： 我们的目标是找到 $\max_{1 \le i \le n, \max(1, i-k+1) \le j \le i}$ $\sum_{l=j}^{i} w_l$。 使用前缀和，这等价于找到 $\max_{1 \le i \le n} (P[i] - P[j-1])$，其中 $j-1$ 的范围是 $[\max(0, i-k), i-1]$。 对于每一个固定的右端点 $i$，我们想让 $P[i]$ 减去一个尽可能小的 $P[j-1]$。所以问题变成了：

   

3. 单调队列优化： 当我们从 $i$ 移动到 $i+1$ 时，寻找最小值的窗口 $[\max(0, i-k), i-1]$ 也随之滑动。我们可以使用一个双端队列（deque）来维护这个滑动窗口内的最小前缀和值的索引。

   • 队列中存储的是前缀和数组 $P$ 的索引。
   • 队列中的索引 $j$ 对应的 $P[j]$ 值是单调递增的。
   • 遍历 $i$ 从 $1$ 到 $n$： a. 移除队首：检查队首的索引 dq.front() 是否已经滑出窗口（即 dq.front() < i - k）。如果是，则从队首弹出。 b. 计算当前最大和：此时，队首元素 dq.front() 就是当前窗口 $[i-k, i-1]$ 中 P 值最小的索引。我们用 $P[i] - P[\text{dq.front()}]$ 来更新全局的最大和。 c. 维护单调性：从队尾开始，如果 $P[\text{dq.back()}] \ge P[i]$，就将其弹出。这保证了队列中 $P$ 值的单调递增性。 d. 入队：将当前索引 $i$ 加入队尾。

这个过程对每个元素处理一次，所以时间复杂度是 $O(n)$。

C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <deque>

// a_i 的最大值
const int MAX_A = 10000001;
// spf[i] 存储 i 的最小质因子 (Smallest Prime Factor)
int spf[MAX_A];

// 使用筛法预处理所有小于 MAX_A 的数的最小质因子
void sieve() {
    // 初始化 spf[i] = i
    std::iota(spf, spf + MAX_A, 0);
    for (int i = 2; i * i < MAX_A; ++i) {
        // 如果 i 是一个质数 (其最小质因子是它自己)
        if (spf[i] == i) {
            // 遍历 i 的倍数 j，并更新它们的最小质因子
            for (int j = i * i; j < MAX_A; j += i) {
                if (spf[j] == j) { // 如果 j 的最小质因子还未被标记
                    spf[j] = i;
                }
            }
        }
    }
}

// 计算数字 x 的重量
int get_weight(int x) {
    if (x == 1) return 0;
    int max_exp = 0;
    while (x > 1) {
        int p = spf[x]; // 获取 x 的最小质因子
        int current_exp = 0;
        // 计算质因子 p 的指数
        while (x > 1 && x % p == 0) {
            current_exp++;
            x /= p;
        }
        // 更新最大指数
        if (current_exp > max_exp) {
            max_exp = current_exp;
        }
    }
    return max_exp;
}

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    std::vector<long long> weights(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        weights[i] = get_weight(a[i]);
    }

    // 计算重量数组的前缀和
    std::vector<long long> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + weights[i];
    }

    long long max_weight_sum = 0;
    // 使用单调队列寻找长度不超过 k 的最大子段和
    std::deque<int> dq;
    dq.push_back(0); // 初始窗口，对应 P[0]

    for (int i = 1; i <= n; ++i) {
        // 移除滑出窗口的队首索引
        if (!dq.empty() && dq.front() < i - k) {
            dq.pop_front();
        }

        // 计算以 i 结尾的子数组的最大和，并更新全局最大值
        // P[dq.front()] 是当前窗口内最小的前缀和
        max_weight_sum = std::max(max_weight_sum, prefix_sum[i] - prefix_sum[dq.front()]);

        // 维护队列的单调性（对应的前缀和值单调递增）
        while (!dq.empty() && prefix_sum[dq.back()] >= prefix_sum[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    std::cout << max_weight_sum << "\n";
}

int main() {
    // 提高 IO 效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 全局一次性预处理
    sieve();

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Python

import sys
from collections import deque

# a_i 的最大值
MAX_A = 10000001
# spf[i] 存储 i 的最小质因子
spf = list(range(MAX_A))

# 使用筛法预处理所有小于 MAX_A 的数的最小质因子
def sieve():
    for i in range(2, int(MAX_A**0.5) + 1):
        # 如果 i 是一个质数
        if spf[i] == i:
            # 遍历 i 的倍数 j，并更新它们的最小质因子
            for j in range(i * i, MAX_A, i):
                if spf[j] == j:
                    spf[j] = i

# 计算数字 x 的重量
def get_weight(x):
    if x == 1:
        return 0
    max_exp = 0
    while x > 1:
        p = spf[x] # 获取 x 的最小质因子
        current_exp = 0
        # 计算质因子 p 的指数
        while x > 1 and x % p == 0:
            current_exp += 1
            x //= p
        # 更新最大指数
        if current_exp > max_exp:
            max_exp = current_exp
    return max_exp

def solve():
    n, k = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    weights = [get_weight(num) for num in a]

    # 计算重量数组的前缀和
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + weights[i]

    max_weight_sum = 0
    # 使用单调队列寻找长度不超过 k 的最大子段和
    dq = deque([0]) # 初始窗口，对应 P[0]

    for i in range(1, n + 1):
        # 移除滑出窗口的队首索引
        if dq and dq[0] < i - k:
            dq.popleft()
        
        # 计算以 i 结尾的子数组的最大和，并更新全局最大值
        max_weight_sum = max(max_weight_sum, prefix_sum[i] - prefix_sum[dq[0]])

        # 维护队列的单调性
        while dq and prefix_sum[dq[-1]] >= prefix_sum[i]:
            dq.pop()
        dq.append(i)
        
    print(max_weight_sum)

# 全局一次性预处理
sieve()

# 读取测试用例数量
T = int(sys.stdin.readline())
for _ in range(T):
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    // a_i 的最大值
    static final int MAX_A = 10000001;
    // spf[i] 存储 i 的最小质因子
    static int[] spf = new int[MAX_A];

    // 使用筛法预处理所有小于 MAX_A 的数的最小质因子
    static void sieve() {
        for (int i = 0; i < MAX_A; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i < MAX_A; i++) {
            // 如果 i 是一个质数
            if (spf[i] == i) {
                // 遍历 i 的倍数 j，并更新它们的最小质因子
                for (int j = i * i; j < MAX_A; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
    }

    // 计算数字 x 的重量
    static int getWeight(int x) {
        if (x == 1) return 0;
        int maxExp = 0;
        while (x > 1) {
            int p = spf[x]; // 获取 x 的最小质因子
            int currentExp = 0;
            // 计算质因子 p 的指数
            while (x > 1 && x % p == 0) {
                currentExp++;
                x /= p;
            }
            // 更新最大指数
            if (currentExp > maxExp) {
                maxExp = currentExp;
            }
        }
        return maxExp;
    }

    static void solve(BufferedReader br) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] a = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        long[] weights = new long[n];
        for (int i = 0; i < n; i++) {
            weights[i] = getWeight(a[i]);
        }

        // 计算重量数组的前缀和
        long[] prefixSum = new long[n + 1];
        prefixSum[0] = 0;
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + weights[i];
        }

        long maxWeightSum = 0;
        // 使用单调队列寻找长度不超过 k 的最大子段和
        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(0); // 初始窗口，对应 P[0]

        for (int i = 1; i <= n; i++) {
            // 移除滑出窗口的队首索引
            if (!dq.isEmpty() && dq.peekFirst() < i - k) {
                dq.pollFirst();
            }

            // 计算以 i 结尾的子数组的最大和，并更新全局最大值
            maxWeightSum = Math.max(maxWeightSum, prefixSum[i] - prefixSum[dq.peekFirst()]);

            // 维护队列的单调性
            while (!dq.isEmpty() && prefixSum[dq.peekLast()] >= prefixSum[i]) {
                dq.pollLast();
            }
            dq.addLast(i);
        }
        System.out.println(maxWeightSum);
    }

    public static void main(String[] args) throws IOException {
        // 全局一次性预处理
        sieve();
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            solve(br);
        }
    }
}

题目内容

一个大于 $1$ 的正整数 $x$ 的重量定义为：将其分解质因数之后得到的最大的指数。例如，$90= 2^1×3^2×5^1$ ，它的重量为 $max${$1,2,1$}$=2$ 。

现在，给定 $n$ 个整数 $a_1,a_2,…,a_n$ ，小歪想找到这样不超过 $k$ 个连续的位置，满足：它们上面数字的重量之和是最大的。你只需要输出这个最大的重量之和即可。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦ T ≦ 2 × 10^5)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,k(1 ≦k≦n≦2× 10^5)$ ，代表整数序列的长度、最多选择连续整数的个数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(2 ≦ a_i≦ 10^7)$ ，代表整数序列。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 × 10^5$ 。

输出描述

对于每组测试数据，新起一行。输出一个整数，代表最大的重量之和。

样例1

输入

3
7 3
4 6 5 8 1 3 2 9
5 5
2 2 2 2 9
2 1
6 8

输出

5
6
3

说明

对于第一组数据，各个数字的重量依次为：$2,1,1,3,1,1,2$ 。选择区间 $[3,5]$ (下标从 $1$ 开始计)即可。