「Codeforces 402D」Upgrading Array

题目链接: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;
}

发表评论