\[\text{NOIP模拟赛-2023.10.11} \]
T1 染色
给定 \(n\)，需要给整数 \(1\sim n\) 染色，使得对于所有 \(1\leq i\leq j\leq n\)，若 \(j-i\) 为质数，则 \(i,j\) 不同色。求颜色最少的染色方案，输出任意一种方案
\(1\leq n\leq 10000\)
诈骗题
观察到若 \(j=i+4\) 则 \(i,j\) 可同色，所以答案上界为 \(4\)，而样例中 \(n=7\) 的答案已经是 \(4\)，所以 \(n\ge 7\) 的全都是 \(4\)，小于 \(7\) 的打表即可
code
#pragma optimize GCC(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n;
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
// fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
scanf("%d",&n);
if(n==1)
printf("1\n1");
else if(n==2)
printf("1\n1 1");
else if(n==3)
printf("2\n1 1 2");
else if(n==4)
printf("2\n1 1 2 2");
else if(n==5)
printf("3\n1 1 2 2 3");
else if(n==6)
printf("3\n1 1 2 2 3 3");
else
{
puts("4");
for(int i=1; i<=n; i++)
printf("%d ",i%4+1);
}
return 0;
}