自动搬运

查看原文

来自洛谷，原作者为

	ycx303 **

搬运于2025-08-24 22:22:46，当前版本为作者最后更新于2025-03-25 21:03:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6650 「SWTR-5」Sequence题解

思路：

思路非常的简短，对于 $k$ 的限制，双指针即可。

然后对于当前区间的答案，显然我们维护每个质因子的个数即可。

假设质因子为 $n$ 个，显然我们 $1, 2, 3, 4\dots$ 这样分配是最优的。

代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 10;
int n, a[N], k, res, ans, cnt[N], mx, vis[N], pos = 1, val[N];
vector<int> v[N];
multiset<int> s;
inline int calc(int x) {
	int l = 1, r = 1e4;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (mid * (mid + 1) <= x * 2) l = mid;
		else r = mid - 1;
	}
	return x + l;
}
inline void add(int x) {
	s.insert(x);
	int y = x;
	for (int i : v[x]) {
		int tmp = 0;
		while (y % i == 0)	y /= i, tmp++;
		res += val[cnt[i] + tmp] - val[cnt[i]];
		cnt[i] += tmp;
	}
}
inline void del(int x) {
	s.erase(s.lower_bound(x));
	int y = x;
	for (int i : v[x]) {
		int tmp = 0;
		while (y % i == 0)	y /= i, tmp++;
		res += val[cnt[i] - tmp] - val[cnt[i]];
		cnt[i] -= tmp;
	}
}
signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i], mx = max(mx, a[i]);
	for (int i = 2; i <= mx; i++) if (!vis[i]) {
			for (int j = i; j <= mx; j += i) v[j].push_back(i), vis[j] = 1;
		}
	for (int i = 1; i <= 2e6; i++) val[i] = calc(i);
	for (int i = 1; i <= n; i++) {
		add(a[i]);
		while ((*--s.end()) - *s.begin() > k) del(a[pos++]);
		ans = max(ans, res);
	}
	cout << ans;
	return 0;
}