题解 CF584D 【Dima and Lisa】

MVP_Harry · 2020-11-01 05:13:01 · 题解

感觉前几个题解完全没有说到点子上。。。

这个题正解的复杂度是对的，虽然我也是看了官方题解之后才知道的。 利用的关键性质是这样的：对于两个素数p_1, p_2 \le 10^9, |p_1 - p_2| < 300. 实际上，最大的差值为282. 同时，我们可以发现对于一个小于三百的偶数，一定能被表示成两个素数的和。

因此，可以得出如下的解法：先找一个最大的，满足p < N - 1的素数。这一部分复杂度为O(k\sqrt{N})，其中最坏情况下，k = 282。而剩下的N - p为偶数，且小于三百，可以直接暴力枚举，复杂度也为O(k\sqrt{N})，跑过绰绰有余。

不过感觉这题出的一般，毕竟还是挺玄学的。

代码如下：

#include<bits/stdc++.h>
#define ll long long
#define rep(i, m, n) for (int i = m; i <= n; i++)
#define per(i, m, n) for (int i = m; i >= n; i--)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define INF 0x3f3f3f3f
using namespace std;

int check(int p) {
    if (p == 1) return 0;
    for (int i = 2; i * i <= p; i++)
        if (p % i == 0) return 0;
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N;
    cin >> N;
    int p1, p2, p3;
    if (check(N)) {
        cout << 1 << "\n" << N << "\n";
        return 0;
    }
    if (check(N - 2)) {
        cout << 2 << "\n" << 2 << " " << N - 2 << "\n";
        return 0;
    }
    for (int i = N - 2; i >= 2; i--) {
        if (check(i)) {
            p1 = i;
            break;
        }
    }
    int remain = N - p1;
    rep(i, 2, remain / 2) if (check(i) && check(remain - i)) {
        p2 = i, p3 = remain - i;
    }
    cout << 3 << "\n" << p1 << " " << p2 << " " << p3 << "\n";
    return 0;
}