CF45G Prime Problem
构造好题。
构造题常规操作：对于某些不知道有没有可能无解的题，大胆猜测一定有解。不要上来就骗分输出无解。
接下来我们慢慢分析做法。
定义 sum 为这个数列的和。
分一组
最简单的情况。 sum 为质数。
那么用等差数列求和求出来之后直接判断一下即可。
分两组
-
引入哥德巴赫猜想。
好像已经证明了哥德巴赫猜想在某个挺大的范围内是正确的了，具体我也不太清楚。
我觉得是它一定是对的。
于是带着这种信念，枚举其中较小的质数，然后把它单独拎出来分一个组即可。
较小的质数一定小于 n ，我不会证明。
-
分三组
考虑让 $sum$ 变成偶数，由于最小的奇质数是 $3$ ，所以多分一组给 $3$ ，然后按照偶数情况处理。
---
至此可以发现我们已经讨论完了所有情况，不存在无解的情况。
```cpp
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n,sum,ans[6010];
inline bool is_prime(int x)
{
if(x < 2) return false;
for(int i=2;i*i<=x;i++) if(x%i == 0) return false;
return true;
}
inline void draw(int x)
{
for(int i=2;i<=x>>1;i++)
if(ans[i] == 1 && is_prime(i) && is_prime(x-i)) {ans[i]=2; return ;}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d",&n);
sum=(n*(n+1))>>1;
for(int i=1;i<=n;i++) ans[i]=1;
if(!is_prime(sum))
{
if(sum&1)
{
if(is_prime(sum-2)) ans[2]=2;
else {ans[3]=3; draw(sum-3);}
}
else draw(sum);
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
// fclose(stdin); fclose(stdout);
return 0;
}
```
线性筛没必要，实测根号暴力甚至更快。
## $\text{Thank you for your reading!}
您的点赞和评论是对作者最大的支持！