解题思路

先求出每个数的指数强度，再在强度序列上求长度不超过 $k$ 的最大连续子段和。

指数强度是质因数分解中的最大指数。由于 $a_i\le 10^7$ 且 $\sum n\le 2\times 10^5$ ，用筛法预处理每个数的最小质因子 spf，再沿最小质因子分解并记录最大指数，单个数约为 $O(\log a_i)$ 。

得到强度序列 $w$ 后，用前缀和 $P$ 把子段和写成 $P[i]-P[j]$ ，其中 $i-k\le j<i$ 。对每个右端点 $i$ ，需要窗口内最小的前缀和。用单调队列维护该窗口，整体 $O(n)$ 。

复杂度分析

一个大于 1 的正整数 $x$ 的指数强度定义为：将其质因数分解后，各质因子指数的最大值。例如 $90=2^{1}\times 3^{2}\times 5^{1}$ ，指数强度为 2。

给定长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$ 。请选出一段长度不超过 $k$ 的连续区间，使得区间内各数的指数强度之和最大，并输出这个最大和。

约束：测试组数不超过 2×10^5，单组序列长度不超过 2×10^5，且单个测试文件中序列长度之和不超过 2×10^5。每个数不超过 10^7，且至少为 2。

每个测试文件包含多组数据。第一行一个整数 $T$ ，表示数据组数。