CF584D 【Dima and Lisa】题解

一个很偶然的机遇发现了这道数论题。

竟然抢到了 $ 1A $，挺激动的。毕竟第一次嘛。

废话不多说，看题。

题目不难理解，就是给你一个奇数，让你用至多 $ 3 $ 个质数的和来表示它。

数据范围是 $ 10^9 $，乍一看无法用暴力解决此题。

然而我们转念一想：

“ $ CF $ 的机子，emmm”

再仔细看了看，回忆回忆自己学习的数论知识，确定无法用 $ O(1) $ 等时间复杂度较低的方法了（如果有请私信我，评论我有可能看不到）。

然后再想：怎么打暴力？

“一个奇数”、“质数和”

“woc这不是哥德巴赫猜想嘛”

没错，就是哥德巴赫猜想。

把原数减去一个 $ 3 $ ，然后直接暴力求解就星了。

$ m code $

# include <bits/stdc++.h>
inline void xhw();
using namespace std;
inline bool is_prime(int);
int n;
int main() {
    xhw();
    return 0;
}
void xhw() {
    scanf("%d", &n);
    if(n == 3) {
        puts("1");
        puts("3");
        return;
    }
    if(n == 5) {
        puts("1");
        puts("5");
        return;
    }
    if(n == 7) {
        puts("1");
        puts("7");
        return;
    }//先来一堆特判
    puts("3");
    printf("3 ");
    n -= 3; //将n减去3
    for(register int i = 2; i < n - 1; i ++)
        if(is_prime(i) && is_prime(n - i)) { //直接用朴素判断素数算法跑暴力
            printf("%d %d", i, n - i);
            return;
        }
}
inline bool is_prime(int x) {
    for(register int i = 2; i * i <= x; i ++)
        if(x % i == 0) return false;
    return true;
}