Problem 灯
题目大意
n盏灯排成一列，标号一到n，一开始标号为1的灯亮着。
现在依次对于2~n的每一个质数pi，指定一盏亮着的灯ai，点亮所有标号为$A[i]pm kP_i$的灯。
有spj，任意一种方案即可。
输入一个整数n，输出点灯方案。
Solution
首先写个暴力，考虑一下小范围的数据。
我们发现$n<16$的时候没有完美解，都是n-1。再算下去，发现$n>16$的时候任意一组都有完美解。
我们分析一下这个玩意儿。
把一到n的灯集体下标前移1，变成0~n-1。这时候当我们点亮第一盏灯，所有偶数都被点亮了。
接下来我们从前面的打表知道，如果所有灯都在1点亮，那么只有2不会亮。前移了以后就是只有1不会亮。
这时候我们要想一下怎么点亮这个一。
现在若找到两个质数$P_i<P_j$，使得$P_i^2>=n&P_i+P_j<n&P_j=kP_i+1$
一开始绝对已经点亮了pi+1，因为其是偶数。
在pj位置时选择pi+pj标号的即可。
证明：
所有不为$P_i^{A_i}*P_j^{A_j}$的标号一定被点亮过。
因为$P_i^2>n$，所以受影响的标号只有1,pi,pj.
其中，因为$P_j=kP_i+1$
1在pi时被点亮，pi在pj时被点亮，pj在pi时被点亮。
至此，我们搞定了1且没有影响到其它。
这种方法对于n不为26..34时有效，这一些就暴力手算好了，不难。
对于小于16的情况进行特判即可。
AC Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int cheat[11][15]={ 7 {0,1,1,4,5,7,7,25,25,25}, 8 {0,1,1,4,5,7,7,25,25,25}, 9 {0,1,1,4,5,7,7,25,25,25}, 10 {0,1,1,4,5,7,7,19,27,29,29}, 11 {0,1,1,7,13,2,1,1,27,3,1}, 12 {0,1,1,1,4,13,1,3,31,31,1,1}, 13 {0,1,1,1,4,13,1,3,31,31,1,1}, 14 {0,1,1,1,4,13,1,3,31,31,1,1}, 15 {0,1,1,1,4,13,1,3,31,31,1,1} 16 }; 17 int n,p[1000010],tot=0; 18 bool np[1000010]; 19 int main(){ 20 scanf("%d",&n); 21 for(int i=2;i<=n;i++) 22 if(!np[i]){ 23 p[++tot]=i;np[i]=1; 24 if((long long)i*i<=n) 25 for(int j=i*i;j<=n;j+=i)np[j]=1; 26 } 27 printf("%d %d ",tot,(n<=16)?n-1:n); 28 if(n<=16) 29 for(int i=1;i<=tot;i++)printf("1 "); 30 else if(n>=26&&n<=34) 31 for(int i=1;i<=tot;i++)printf("%d ",cheat[n-26][i]); 32 else{ 33 int t=1,x=0,y=0; 34 while(p[t]*p[t]<n)t++; 35 for(int i=t;i<=tot;i++){ 36 for(int j=i+1;p[i]+p[j]<n;j++) 37 if(p[j]%p[i]==1){ 38 x=i;y=j; 39 break; 40 } 41 if(x||y)break; 42 } 43 for(int i=1;i<=tot;i++){ 44 if(i==x)printf("%d ",p[i]+2); 45 else if(i==y)printf("%d ",p[i]+p[x]+1); 46 else printf("1 "); 47 } 48 } 49 return 0; 50 }