是时候水点NOIP题了呢
好吧bzoj上的数据经过加强，两个质数是糊弄不过去的
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=105,M=10005,INF=100000000,pri[]={13331,24841,23333,23909,23339};
int n,m,a[N],num[M],len,ans,w[M*3][5],pr[N][5];
char s[M];
queue<int> Q;
inline void Read(int x){
scanf("%s",s+1);len=strlen(s+1);
if(s[1]=='-'){a[x]=1;for(register int i=2;i<=len;i++)num[i-1]=s[i]-'0';len--;}
else for(register int i=1;i<=len;i++)num[i]=s[i]-'0';
for(register int i=1;i<=len;i++){
for(register int j=0;j<5;j++){pr[x][j]=(pr[x][j]<<3)+(pr[x][j]<<1)+num[i];if(pr[x][j]>=INF)pr[x][j]%=pri[j];}
}
for(register int i=0;i<5;i++)pr[x][i]%=pri[i];
}
inline void Prepare(){
for(register int i=0;i<5;i++){
for(register int j=0;j<pri[i];j++){
for(register int k=n;k>=0;k--){
w[j][i]=(w[j][i]*j+(a[k]?pri[i]-pr[k][i]:pr[k][i]))%pri[i];
}
}
}
}
inline bool Check(int t){return w[t%pri[0]][0] || w[t%pri[1]][1] || w[t%pri[2]][2] || w[t%pri[3]][3] || w[t%pri[4]][4];}
int main(){
freopen("3751.in","r",stdin);
freopen("3751.out","w",stdout);
scanf("%d %d",&n,&m);
for(register int i=0;i<=n;i++)Read(i);
Prepare();
for(register int i=1;i<=m;i++)if(!Check(i))ans++,Q.push(i);
printf("%d\n",ans);
while(!Q.empty()){printf("%d\n",Q.front());Q.pop();}
return 0;
}
评论 (0)
