第九届中国大学生程序设计竞赛（秦皇岛）-（CCPC2023-Qinhuangdao）

F - 质数之谜

https://cpc.csgrandeur.cn/csgoj/problemset/problem?pid=1229

1 second / 256 megabytes

standard input / standard output

题目

数学王国的质数部长是质数的狂热追随者，因此他特别设立了一个部门来解决与质数相关的问题。这个部门的负责人罗伯特先生最近收到了他的朋友欧拉的一封信。

这封信中包含了一个关于质数的谜题。欧拉认为序列 $a_1, a_2, ..., a_n$ 是美丽的当且仅当所有元素都是正整数，并且任意两个相邻元素的和是一个质数。

形式化地说，$\forall i\in [1, n] \cap \mathbb{N}, a_i \in \mathbb{N}^+,\forall i\in [1, n) \cap \mathbb{N}, (a_i+a_{i+1}) \in \mathbb{P}$，其中 $\mathbb{P}$ 表示包含所有质数的集合。

有时，欧拉信中给定的序列并不美丽。罗伯特先生希望通过修改最少数量的序列元素使其变得美丽。

罗伯特先生最近很忙，所以他想请你帮忙计算使序列变得美丽的最小修改数量。

输入

第一行包含一个整数 $n\ (2\le n \le 10^5)$。

第二行包含 $n$ 个正整数，表示 $a_1, a_2,...,a_n\ (1\le a_i\le 10^5)$。

输出

输出一个整数，表示使序列变得美丽的最小更新元素数量。

样例

输入

6
1 5 1 4 4 1

输出

2

输入

9
30 6 7 12 15 8 20 17 14

输出

4

解释

对于第一个测试，更新后的序列可以是 “1 2 1 1 4 1”。

题解

孪生素数猜想 / 波利尼亚克猜想

首先介绍一下本题需要用到的重要猜想——孪生素数才行：存在无穷多个素数 $p$，使得 $p+2$ 是素数，素数对 $(p,p+2)$ 成为孪生素数。

波利尼亚克拓展了范围：对于所有自然数 $k$，存在无穷多个素数对 $(p,p+2k)$.

猜想应用

除了偶素数 $2$ 可以被 $1+1$ 凑出，其他情况下素数一定是奇数，那么一定由一奇一偶凑出。

另外，根据上面的猜想，如果 $a,?,b$ 中，若 $a,b$ 同奇偶性（即 $|a-b|=2k$），那么可以找到一种 $?$ 的填法，使左右都能凑出素数（即$|(a+?)-(b+?)|=2k$ 符合孪生质数猜想）。

因此，如果对于序列第 $i$ 位，如果第 $i-1$ 位修改为了除 $1$ 之外的数，那么第 $i$ 位是可以不用修改的，因为两端一定是同奇偶的。

动态规划

因为 $1+1=2$ 的特殊性，所以需要特别判断这种情况。

  • 状态表示：$dp_{ij}:=$ 考虑 $1\sim i$ 区间，且第 $i$ 位为 $j$ 状态所需最小步数。

    • $j=0$：第 $i$ 位不改
    • $j=1$：第 $i$ 位改成 $1$
    • $j=2$：第 $i$ 位改成偶数
    • $j=3$：第 $i$ 位改成奇数（除 $1$）

  • 状态计算：

    • $0\to0$：当且仅当 $a_{i-1}+a_{i}$ 为素数时可转移
    • $1\to0$：当且仅当 $1+a_{i}$ 为素数时可转移
    • $2\to0$：当且仅当 $a_i$ 为奇数时可转移
    • $3\to0$：当且仅当 $a_i$ 为偶数时可转移
    • $0\to1$：当且仅当 $a_{i-1}+1$ 为素数时可转移
    • $1\to1$：恒可转移（$1+1=2$ 恒为素数）
    • $2\to1$：恒可转移
    • $3\to1$：不可转移（奇 + $1$ 不可能为素数）
    • $0\to2$：当且仅当 $a_{i-1}$ 为奇数时可转移
    • $1\to2$：恒可转移
    • $2\to2$：不可转移（偶 + 偶 不可能为素数）
    • $3\to2$：恒可转移
    • $0\to3$：当且仅当 $a_{i-1}$ 为偶数时可转移
    • $1\to3$：不可转移（$1$ + 奇 不可能为素数）
    • $2\to3$：恒可转移
    • $3\to3$：不可转移（奇 + 奇 不可能为素数）

通过上面的转移方式，转移时取最小值即可。对于初值，$dp_{10}=0$，$dp_{11}=dp_{12}=dp_{13}=1$.

时间复杂度为：$O(n)$

转移后，最终答案为：$\min\{dp_{n0},dp_{n1},dp_{n2},dp_{n3}\}$

代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

constexpr int MAXN = 2e5 + 10;
int prime[MAXN], idx;
bool not_prime[MAXN];
int n;
int a[MAXN];
int dp[MAXN][4];

void init_prime()
{
    not_prime[0] = not_prime[1] = true;
    for (int i = 2; i < MAXN; i++)
    {
        if (!not_prime[i])
            prime[idx++] = i;
        for (int j = 0; j < idx && i * prime[j] < MAXN; j++)
        {
            not_prime[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    dp[1][1] = dp[1][2] = dp[1][3] = 1;
    for (int i = 2; i <= n; i++)
    {
        // 0 -> 0
        if (!not_prime[a[i - 1] + a[i]])
            dp[i][0] = min(dp[i][0], dp[i - 1][0]);
        // 1 -> 0
        if (!not_prime[1 + a[i]])
            dp[i][0] = min(dp[i][0], dp[i - 1][1]);
        // 2 -> 0
        if (a[i] % 2)
            dp[i][0] = min(dp[i][0], dp[i - 1][2]);
        // 3 -> 0
        else
            dp[i][0] = min(dp[i][0], dp[i - 1][3]);
        ///////////////////////////////////////////////
        // 0 -> 1
        if (!not_prime[a[i - 1] + 1])
            dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1);
        // 1 -> 1
        dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1);
        // 2 -> 1
        dp[i][1] = min(dp[i][1], dp[i - 1][2] + 1);
        // 3 -> 1: illegal
        ///////////////////////////////////////////////
        // 0 -> 2
        if (a[i - 1] % 2)
            dp[i][2] = min(dp[i][2], dp[i - 1][0] + 1);
        // 1 -> 2
        dp[i][2] = min(dp[i][2], dp[i - 1][1] + 1);
        // 2 -> 2: illegal
        // 3 -> 2
        dp[i][2] = min(dp[i][2], dp[i - 1][3] + 1);
        ///////////////////////////////////////////////
        // 0 -> 3
        if (a[i - 1] % 2 == 0)
            dp[i][3] = min(dp[i][3], dp[i - 1][0] + 1);
        // 1 -> 3: illegal
        // 2 -> 3
        dp[i][3] = min(dp[i][3], dp[i - 1][2] + 1);
        // 3 -> 3: illegal
    }
    cout << min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]}) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init_prime();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}