BZOJ1423 : Optimus Prime

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

设$f[x]$表示为了保证自己可以取到质数$x$，第一步在$[0,n]$中可以选的数是多少。

这个数是唯一的，因为如果存在两个$f[x]=a,b(a<b)$，那么如果先手取了$a$，后手就能取$b$来让先手取不到$x$，矛盾。

如果$x$与下一个质数之间的差值大于$n$，那么$f[x]$就是结果，当$f[x]=0$时先手必败。

对于不超过$n$的$x$，$f[x]=x$。

对于大于$n$的$x,f[x]=f[y]$，其中$y$是$x$前面最近的与它差值大于$n$的质数，可以双指针得到。

如果没有找到终止态，取一定范围内的所有大质数的$f[x]$的众数，极有可能就是精确解。

#include<cstdio>
const int N=3000010,M=N/10,E=1010;
int T,n,t,i,j,tot,p[M],f[M],c[E],ans[E];bool v[N];
inline int cal(int n){
if(~ans[n])return ans[n];
int i,j;
for(i=0;i<=n;i++)c[i]=0;
for(i=j=0;i<=tot;i++){
if(p[i]<=n)f[i]=p[i];
else{
while(j+1<i&&p[i]-p[j+1]>n)j++;
f[i]=f[j];
}
if(i<tot&&p[i]+n<p[i+1])return ans[n]=f[i];
if(i>tot/10*9)c[f[i]]++;
}
for(i=j=0;i<=n;i++)if(c[i]>c[j])j=i;
for(i=0;i<=n;i++)if(i!=j&&c[i]*2>c[j])return ans[n]=0;
return ans[n]=j;
}
int main(){
for(v[1]=1,i=2;i<N;i++){
if(!v[i])p[++tot]=i;
for(j=1;j<=tot&&i*p[j]<N;j++){
v[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
for(i=0;i<E;i++)ans[i]=-1;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
if(t=cal(n))printf("A %d\n",t);else puts("B");
}
return 0;
}