题目描述
你需要找到一个序列 \(A_1, A_2 \dots A_i\dots A_m\)
并且每个 $A_i 都为质数或者 \({1}\) 或者 \({0}\) 使得
\(\sum_{i = 1}^{m}{A_i}\)
对于每个询问,你需要找到最小的 \({m}\)。
数据保证题目有解。
特别的是,如果 \({s=0}\) 那么你也至少需要一个 \({0}\) 来填满它。
数据范围
\(1 \leq s\leq 10^7\)
solution
如果 \(s\) 是个偶数,根据哥德巴赫猜想,它一定可以分解为两个质数的和的形式。
如果是奇数的话就有两种可能,一个是它可以由 \(2\) 和另一个质数相加,这种直接 \(check(n - 2)\) 就好。
另一种是把奇数 \(-1\) 变为偶数,在将这个偶数按照上面分解。
线筛预处理个质数就好了。
code
/*
work by:Ariel_
Sorce:
Knowledge:
Time:
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define rg register
using namespace std;
const int MAXN = 1e7 + 5;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int tot, pre[MAXN];
bool vis[MAXN];
void Pre() {
for(int i = 2; i <= MAXN; i++) {
if(vis[i] == 0) pre[tot++] = i;
for(int j = 0; j <= tot, i * pre[j] <= MAXN; j++){
vis[pre[j] * i] = 1;
if (i % pre[j] == 0)break;
}
}
}
signed main() {
int T = read();
Pre();
while(T--) {
int x = read();
if(x == 0) {cout<<"1\n0 = 0\n";continue;}
if(x == 1) {cout<<"1\n1 = 1\n";continue;}
if(!vis[x]){cout<<"1\n"<<x<<" = "<<x<<"\n";continue;}
int opt = 1;
if(x & 1) {
int fag = 0, z, w;
if(!vis[x - 2]) {
cout<<"2\n";
cout<<"2 + "<<x - 2<<" = "<<x<<"\n";
continue;
}
cout<<"3\n"<<"1 + ";
x--, opt = 0;
}
else cout<<"2\n";
for (int i = 3; i < x; i++)
if (!vis[i] && !vis[x - i]){printf("%d + %d", i, x - i); break;}
if(opt == 0) printf(" = %d\n", x + 1);
else printf(" = %d\n", x);
}
return 0;
}