题意
已知 \(m\) 个坏素数 \(b_i\)，定义一个数 \(x\) 的分值 \(f(x)=f(\frac xp)+k\)，其中 \(p\) 为 \(x\) 的最小质因数，如果 \(p\) 为坏素数则 \(k=-1\)，否则 \(k=1\)，初始 \(f(1)=0\)，一个数组的分值为其中所有数的分值之和。
现在给出 \(n\) 个数 \(a_i\)，你可以反复进行一项操作：把 \(a\) 数组的一个前缀所有数除以它们的最大公约数。问 \(a\) 数组的分值最大是多少。\(n,m\le5\cdot10^3,a_i,b_i\le10^9\)。
题解
首先一个数 \(x\) 的分值可以看出能这样算：先把他质因数分解，然后统计有多少个质因数是坏的，有多少是不坏的，然后用不坏的个数减去坏的个数得到分值。那么我们一次操作肯定是要消掉坏素数，让分数提高的。
然后考虑操作。首先假设 \(a\) 数组的前缀 \(\gcd\) 数组为 \(g\)，那么把 \(g\) 的每一项质因数分解了之后，肯定是前面的项包含了后面的项。
那么如果我们从前往后进行操作的话，假设我们对一个位置进行了操作，即这个前缀都除以了它们的 \(\gcd\)，那么这个前缀的 \(\gcd\) 就变成了 \(1\) 了，之后的也一样变成了 \(1\)，后面的根本操作不了。
而如果我们从后往前地进行操作，就不会有这个问题，而且是明显不会更劣的，因此贪心地从后往前进行操作，如果这次操作能增加答案则进行，否则忽略。
值域 \(1e9\)，因此计算分值的时候直接暴力质因数分解即可，可以加点剪枝。时间复杂度 \(\mathcal O(n^2+n\sqrt{10^9})\)，在 CF 评测姬上可以通过。
个人觉得是道水蓝题。。。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e3 + 10;
int n, m, ans, a[N], b[N], g[N];
unordered_map<int, int> Bad;
inline int gcd(int x, int y) {
return !y ? x : gcd(y, x % y);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i], Bad[b[i]] = 1;
g[1] = a[1];
for (int i = 2; i <= n; i++) g[i] = gcd(g[i - 1], a[i]);
// 前面的 g 肯定包含了后面的 g
for (int i = n; i >= 1; i--) {
int good = 0, bad = 0, t = g[i];
// 不可能同时有两个 > sqrt(x) 的质因子存在
for (int j = 2; j * j <= g[i]; j++) {
if (t == 1) break;
if (t % j != 0) continue;
while (t % j == 0) {
if (Bad.count(j)) bad++;
else good++;
t /= j;
}
}
if (t > 1) {
if (Bad.count(t)) bad++;
else good++;
}
if (good - bad <= 0) { // 等于要不要好像无所谓
for (int j = i; j >= 1; j--)
a[j] /= g[i];
g[1] = a[1];
for (int j = 2; j <= i; j++)
g[j] = gcd(g[j - 1], a[j]);
}
}
for (int i = 1; i <= n; i++) {
int good = 0, bad = 0, t = a[i];
for (int j = 2; j * j <= a[i]; j++) {
if (t == 1) break;
if (t % j != 0) continue;
while (t % j == 0) {
if (Bad.count(j)) bad++;
else good++;
t /= j;
}
}
if (t > 1) {
if (Bad.count(t)) bad++;
else good++;
}
ans += good - bad;
}
cout << ans << "\n";
return 0;
}