感觉和 CF1889C2 Doremy's Drying Plan (Hard Version) 有异曲同工之妙。
显然去除每个数的平方因子后，两个数相乘为完全平方数当且仅当它们相等。
考虑若确定了分段方案，那么修改次数就是，每一段重复出现的数的个数。
那么我们设 \(f_{i, j}\) 为 \([1, i]\) 修改了 \(j\) 次的最小分段次数。然后我们枚举上一个分段点 \(k\)，那么有 \(f_{i, j} \gets f_{k, j - g(k + 1, i)} + 1\)，其中 \(g(l, r)\) 为 \([l, r]\) 中重复出现的数的个数。
显然对于一个 \(j\)，\(f_{\ast, j}\) 单调不降，那么我们可以找到 \(\forall p \in [0, m]\)，使得 \(g(k + 1, i) = p\) 的 \(k\) 的最小值，然后直接从这个 \(k\) 转移过来。
时间复杂度就是 \(O(nk^2)\)。去除平方因子我写了 \(O(n \sqrt{V})\)，也能过。
code
// Problem: E2. Square-Free Division (hard version)
// Contest: Codeforces - Codeforces Round 708 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1497/E2
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int maxm = 3300;
const int N = 3200;
int n, m, a[maxn], pr[maxm], tot, b[maxm], f[maxn][22];
bool vis[maxm];
inline void init() {
for (int i = 2; i <= N; ++i) {
if (!vis[i]) {
pr[++tot] = i;
b[tot] = i * i;
}
for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) {
break;
}
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
for (int j = 1; j <= tot && b[j] <= a[i]; ++j) {
while (a[i] % b[j] == 0) {
a[i] /= b[j];
}
}
}
map<int, int> mp;
set<int> S;
S.insert(0);
for (int i = 1; i <= n; ++i) {
if (mp.find(a[i]) != mp.end()) {
S.insert(mp[a[i]]);
}
mp[a[i]] = i;
auto it = S.end();
vector<int> vc;
do {
vc.pb(*(--it));
} while (it != S.begin() && (int)vc.size() <= m);
for (int j = 0; j <= m; ++j) {
f[i][j] = 1e9;
}
for (int j = 0; j < (int)vc.size(); ++j) {
for (int k = j; k <= m; ++k) {
f[i][k] = min(f[i][k], f[vc[j]][k - j] + 1);
}
}
}
printf("%d\n", *min_element(f[n], f[n] + m + 1));
}
int main() {
init();
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}