CF45G Prime Problem 题解

MuYC · 2021-07-12 17:47:08 · 题解

哥德巴赫猜想:

一个大于 2 的偶数能够表示为两个奇质数的和的形式。

一个 trick:

在 [1,n] 每个数只能用一次的前提下，[1, \frac{(n + 1) \times n}{2}] 的正整数都能表示为 [1,n] 中若干数的和的形式。

关于本题

首先 n \ge 2 一定有解

这道题一定有解（除非 n = 1），证明的话如下：

显然 n = 2 或者 n = 3 的时候 一定有解。

用数学归纳法来看，假设 n 有解，那么考虑假设现在变为 n + 1。

将大于等于 n + 1 的最小的质数设为 P ，那么 P < 2 \times (n + 1) ，也就是意味着 P - (n + 1) 一定位于 [1,n] 中，设为 x，然后我们让 x 与 n + 1 配对，然后 x + 1 和 n 配对以此类推。

因为 P 为奇数，所以只会出现奇数偶数配对，所以一定可以配对完 [x,n + 1]，那么剩下的数变为了 [1,x - 1]，可以发现一定有解。

但是我们构造的时候可以不用这个方法，因为其实本题有个要求就是，如果可行，那么将 [1,n] 要分成尽量少的集合。

哥德巴赫猜想 构造答案。

设 S = \frac{(n + 1) \times n }{2}

• 如果 S 是一个质数，那么所有的数都选在一个集合就好了。

• ps.如何把一个数 $T \in [1,S]$ 拆分为 $[1,n]$ 中若干数的和的形式？就不断的减去小于等于它的最大的那一个 $i$ ($i$ 是 $[1,n]$ 中的正整数)即可。

• 如果 S 是一个奇数，倘若 S - 2 是一个质数，直接分为 2 和 S - 2 两个集合。如果 S - 2 不是一个质数，那么我们把 S - 3，也就是提出一个 3 出来，然后按照哥德巴赫猜想做就完事了。值得注意的是，我们把 3 去掉后，[1,S] 的任意数还是能够被表示出来，这个不难证明。

Code

#include <bits/stdc++.h>
using namespace std;
int n, S;
int pd(int x) {
    for(int i = 2 ; i * i <= x ; i ++) if(x % i == 0) return 0;
    return 1;
}
const int MAXN = 2e7;
int P[1 << 21], tot = 0;
bool bk[MAXN], is[6050];
void GetPrime(int N) {
    for(int i = 2 ; i <= N ; i ++) {
        if(!bk[i]) P[++ tot] = i;
        for(int j = 1 ; j <= tot && P[j] * i <= N ; j ++) {
            bk[P[j] * i] = 1;
            if(i % P[j] == 0) break;
        }
    }
    return ;
}

int main() {
    cin >> n; S = (n + 1) * n >> 1, GetPrime(18003000);
    if(pd(S) == 1) { for(int i = 1 ; i <= n ; i ++) printf("1 "); return 0;}
    if(S % 2 == 1 && pd(S - 2) == 0) {
        S -= 3;
        int t = 1;
        for(int i = 1 ; i <= tot ; i ++) 
        if(bk[S - P[i]] == 0) { t = i; break; }
        S = P[t];
        for(int i = n ; i >= 1 ; i --) 
        if(S - i >= 0 && i != 3) S -= i, is[i] = 1;
        for(int i = 1 ; i <= n ; i ++) {
            if(i == 3) { printf("1 "); continue; }
            is[i] ? printf("2 ") : printf("3 "); 
        }
    }
    else if(S % 2 == 1 && pd(S - 2) == 1) 
    for(int i = 1 ; i <= n ; i ++) i == 2 ? printf("2 ") : printf("1 ");
    else {
        int t = 1;
        for(int i = 1 ; i <= tot ; i ++) 
        if(bk[S - P[i]] == 0) { t = i; break; }
        S = P[t];
        for(int i = n ; i >= 1 ; i --) 
        if(S - i >= 0) S -= i, is[i] = 1;
        for(int i = 1 ; i <= n ; i ++)
        is[i] ? printf("1 ") : printf("2 "); 
    }
    return 0;
}