CF1497E2 Square-free division (hard version)

chrisgr · 2025-10-02 14:23:33 · 题解

某模拟赛 T2，自己做法是 \operatorname{O}(n \cdot k) 时间复杂度，发现题解是 \operatorname{O}(n \cdot k ^ 2) 时间复杂度的，且原题题解区中没有 \operatorname{O}(n \cdot k) 做法，意识到爆标，遂来写题解。

首先，发现可以把每个数的平方因子去掉，之后即可通过比较两数是否相等来判断两数之积是否为完全平方数。

于是，可以设置动规状态为 dp_{i,j} 表示以第 i 个数为结尾，修改了 j 次的最小段数。我们发现这个状态无法转移，所以我们可以再记录一个值 st_{i,j} 表示 dp_{i,j} 最小时，最后一个段的开头的下标最大是多少。发现做法正确，愉快爆标。

code

#include<bits/stdc++.h>
using namespace std;
#define V 10000005
#define N 200005
int n, k, p[670000], a[N], bok[V], dp[N][25], st[N][25];
bool book[V];
inline void init() {
    for(int i = 2; i < V; ++i) {
        if(!book[i]) p[++p[0]] = i;
        for(int j = 1; j <= p[0] && 1ll * p[j] * i < V; ++j) {
            book[p[j] * i] = 1;
            if(!(i % p[j])) break;
        }
    }
}
int main() {
    //freopen("seq.in", "r", stdin);
    //freopen("seq.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        for(int i = 1; i <= n; ++i) {
            a[i] = 1;
            int now;
            cin >> now;
            for(int j = 1; book[now]; ++j) {
                if(!(now % p[j])) {
                    bool aa = 0;
                    while(!(now % p[j])) aa = !aa, now /= p[j];
                    if(aa) a[i] *= p[j];
                }
            }
            if(now) a[i] *= now;
            int lst = bok[a[i]];
            for(int j = k; ~j; --j) dp[i][j] = dp[i - 1][j] + 1, st[i][j] = i;
            for(int j = 0; j <= k; ++j) {
                if(lst < st[i - 1][j]) {
                    if(dp[i - 1][j] < dp[i][j]) dp[i][j] = dp[i - 1][j], st[i][j] = st[i - 1][j];
                    else if(dp[i - 1][j] == dp[i][j]) st[i][j] = max(st[i - 1][j], st[i][j]);
                } else {
                    if(dp[i - 1][j] < dp[i][j + 1]) dp[i][j + 1] = dp[i - 1][j], st[i][j + 1] = st[i - 1][j];
                    else if(dp[i - 1][j] == dp[i][j + 1]) st[i][j + 1] = max(st[i - 1][j], st[i][j + 1]);
                }
            }
            //cout << i << "  " << lst << "  " << a[i] << endl;
            //for(int j = 0; j <= k; ++j) cout << j << "  " << dp[i][j] << "  " << st[i][j] << endl;
            bok[a[i]] = i;
        }
        for(int i = n; i; --i) bok[a[i]] = 0;
        int ans = 0x7fffffff;
        for(int i = k; ~i; --i) if(st[n][i]) ans = min(ans, dp[n][i]);
        printf("%d\n", ans);
    }
    return 0;
}