又要开始一段搜索的路程了。
最近看了这题，在网上看到一个结论，任何一个数倍数都能被不超过两个数字组成，假如一个数n个A%x=b,那么必然有m个A%=b那么此时n个A减去m个B就能够被x整除，那么此时就有了上述的结论，在配合上余数来进行一个搜索，就是把余下的数字作为一个状态来进行广搜。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using std::queue;
int const N = ;
int const M = ;
int cnt[M],father[M],record[M];
char ans[M],tmp[M];
int n,k,a1,t1,e[N],c;
bool bfs()
{
queue<int> q;
while(!q.empty())q.pop();
for(int i=;i<c;i++)
{
if(!e[i]||cnt[e[i]%n])continue;
cnt[e[i]%n]=;
father[e[i]%n]=-;
record[e[i]%n]=e[i];
q.push(e[i]%n);
}
while(!q.empty())
{
int num=q.front();
q.pop();
if(a1>&&cnt[num]>a1)return false;
if(num==)return true;
for(int i=;i<c;i++)
{
int nt=(num*k+e[i])%n;
if(!cnt[nt])
{
cnt[nt]=cnt[num]+;
father[nt]=num;
record[nt]=e[i];
q.push(nt);
}
}
}
return false;
}
bool cmp()
{
if(a1==)return true;
if(t1>a1)return false;
if(t1<a1)return true;
for(int i=;i<t1;i++)
{
if(ans[i]>tmp[i])return true;
if(ans[i]<tmp[i])return false;
}
return false;
}
void over()
{
for(int i=;i<t1;i++)
ans[i]=tmp[i];
ans[t1]='\0';
a1=t1;
}
void display(int i)
{
tmp[cnt[i]-]=record[i]+'';
if(father[i]!=-)
display(father[i]);
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
a1=;
for(int i=;i<k;i++)
{
memset(cnt,,sizeof(cnt));
e[]=i,c=;
if(bfs())
{
display();
t1=cnt[];
if(cmp())over();
}
}
if(a1==)
for(int i=;i<k;i++)
{
for(int j=;j<i;j++)
{
memset(cnt,,sizeof(cnt));
e[]=j,e[]=i,c=;
if(bfs())
{
display();
t1=cnt[];
if(cmp())over();
}
}
}
for(int i=;i<a1;i++)printf("%c",ans[i]);
printf("\n");
}
return ;
}