struct haha
{
int len;
int num[555];
}q,temp;
bool vis[5555];
int judge(struct haha &p)//计算其除以n的余数
{
int len=p.len,tmp=0;
for(int i=1;i<=len;i++)
{
tmp=(tmp*x+p.num[i])%n;
}
return tmp;
}
void print(struct haha &p)//找到后输出
{
for(int i=1;i<=q.len;i++)
{
printf("%X",q.num[i]);//输出大写的用X
}
printf("\n");
return ;
}
void BFS()
{
int i;
memset(vis,0,sizeof(vis));
queue
for(i=1;i<16;i++)
{
if(xx[i]==true)
{
q.len=1;
q.num[1]=i;
int k=judge(q);
if(k==0)
{
print(q);
return ;
}
else vis[k]=1;
que.push(q);
}
}
while(!que.empty())
{
temp=que.front();
que.pop();
for(i=0;i<16;i++)
{
q=temp;
q.len+=1;
q.num[q.len]=i;
int k=judge(q);
if(k!=0)
{
if(!vis[k]&&q.len<=500)
{
vis[k]=true;
que.push(q);
}
}
else
{
print(q);
return ;
}
}
}
printf("give me the bomb please\n");
}
int main()
{
int cas,i;
scanf("%d",&cas);
while(cas--)
{
memset(xx,0,sizeof(xx));
scanf("%d %d %d",&n,&x,&m);
for(i=0;i
int k;
scanf("%x",&k);//用%x输入 省去了转化为数字的繁琐
xx[k]=1;
}
if(n==0)
{
if(xx[0]==true)
printf("0\n");
else printf("give me the bomb please\n");
continue;
}
BFS();
}
return 0;
}
另外 本题最多有5000个状态 每个状态最长为500个数字 即500个int 每个int为32位 即4B
那么总共有5000*500*4/1024 KB 不会超过题目限制内存 32768KB
by hnust_xiehonghao