题目链接：Codeforces 402D

你有一个长度为 $n$ 的正整数数组 $a_1,a_2,\cdots,a_n$ 和 $m$ 个坏的质数 $b_1,b_2,\cdots,b_m$，其余的质数称为好的。数组 $a$ 的美丽度定义为 $\sum_{i=1}^n f(a_i)$，其中 $f(x)$ 为如下定义：

$$ f(x)=\begin{cases} 1 & x=1 \\ f(\frac{x}{p})+1 & p\ \text{为}\ x\ \text{的最小质因子},p\ \text{是好的质数} \\ f(\frac{x}{p})-1 & p\ \text{为}\ x\ \text{的最小质因子},p\ \text{是坏的质数} \end{cases} $$

你可以进行无限次操作，每次操作为如下形式：

• 选择一个数字 $r$ 满足 $1\le r\le n$，计算出 $g=\gcd(a_1,a_2,\cdots,a_r)$。
• 对于所有的整数 $i\in [1,r]$，将所有的 $a_i$ 除以 $g$。

经过若干次操作，求出数组 $a$ 美丽度的最大值。

数据范围：$1\le n,m\le 5\times 10^3$，$1\le a_i,b_i\le 10^9$。

Solution

我们考虑贪心，但是不能有后效性。发现可以从后往前贪心，对于当前的 $i$，如果对 $1$ 到 $i$ 操作可以使得答案更优那么就一定操作，对后面的数字操作一定不会对前面数字的决策产生影响（即没有后效性）。

考虑每个数除去 $x$ 对答案的影响。为了方便分析，我们定义一个函数 $g(x)$，这个函数的定义域为 $x\in\text{prime}$：

$$ g(x)=\begin{cases} 1 & x\ \text{是好的质数} \\ -1 & x\ \text{是坏的质数} \end{cases} $$

那么我们有：

$$ f(x)=\sum_{p\in x\ \text{的质因子集合}} g(p) $$

转换后我们可以得到，除以 $x$ 后答案会减去 $i\times f(x)$。可以在 $\mathcal O(\sqrt x)$ 的时间内求出单个 $f(x)$ 的值。

对于 $\gcd$ 的问题，我们可以很轻松地维护前缀 $\gcd$。

时间复杂度：$\mathcal O(n\sqrt{a_i})$。

Code

#include <cstdio>
#include <algorithm>
#include <unordered_map>

const int N = 5e3 + 5, M = 4e4 + 5;

int n, m, tot, a[N], g[N], p[M];
bool flg[M];
std::unordered_map<int, bool> bad;

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!flg[i]) p[++tot] = i;
        for (int j = 1; j <= tot && i * p[j] <= n; j++) {
            flg[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
}
int calc(int x) {
    int ans = 0;
    for (int i = 1; i <= tot && p[i] * p[i] <= x; i++) {
        while (x % p[i] == 0) {
            x /= p[i];
            ans += (bad[p[i]] ? -1 : 1);
        }
    }
    if (x > 1) ans += (bad[x] ? -1 : 1);
    return ans;
}
int main() {
    sieve(M - 5);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        bad[x] = true;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        g[i] = std::__gcd(g[i - 1], a[i]);
        ans += calc(a[i]);
    }
    for (int pro = 1, i = n; i >= 1; i--) {
        int now = calc(g[i] /= pro);
        if (now < 0) {
            ans -= i * now;
            pro *= g[i];
        }
    }
    printf("%d\n", ans);
    return 0;
}