题解：P6650 「SWTR-5」Sequence

ycx303 · 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;
}