又要开始一段搜索的路程了。
最近看了这题，在网上看到一个结论，任何一个数倍数都能被不超过两个数字组成，假如一个数n个A%x=b,那么必然有m个A%=b那么此时n个A减去m个B就能够被x整除，那么此时就有了上述的结论，在配合上余数来进行一个搜索，就是把余下的数字作为一个状态来进行广搜。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<queue> 6 using std::queue; 7 int const N = 15; 8 int const M = 61000; 9 int cnt[M],father[M],record[M]; 10 char ans[M],tmp[M]; 11 int n,k,a1,t1,e[N],c; 12 bool bfs() 13 { 14 queue<int> q; 15 while(!q.empty())q.pop(); 16 for(int i=0;i<c;i++) 17 { 18 if(!e[i]||cnt[e[i]%n])continue; 19 cnt[e[i]%n]=1; 20 father[e[i]%n]=-1; 21 record[e[i]%n]=e[i]; 22 q.push(e[i]%n); 23 } 24 while(!q.empty()) 25 { 26 int num=q.front(); 27 q.pop(); 28 if(a1>0&&cnt[num]>a1)return false; 29 if(num==0)return true; 30 for(int i=0;i<c;i++) 31 { 32 int nt=(num*k+e[i])%n; 33 if(!cnt[nt]) 34 { 35 cnt[nt]=cnt[num]+1; 36 father[nt]=num; 37 record[nt]=e[i]; 38 q.push(nt); 39 } 40 } 41 } 42 return false; 43 } 44 bool cmp() 45 { 46 if(a1==0)return true; 47 if(t1>a1)return false; 48 if(t1<a1)return true; 49 for(int i=0;i<t1;i++) 50 { 51 if(ans[i]>tmp[i])return true; 52 if(ans[i]<tmp[i])return false; 53 } 54 return false; 55 } 56 void over() 57 { 58 for(int i=0;i<t1;i++) 59 ans[i]=tmp[i]; 60 ans[t1]=' '; 61 a1=t1; 62 } 63 void display(int i) 64 { 65 tmp[cnt[i]-1]=record[i]+'0'; 66 if(father[i]!=-1) 67 display(father[i]); 68 } 69 int main() 70 { 71 while(scanf("%d %d",&n,&k)!=EOF) 72 { 73 a1=0; 74 for(int i=1;i<k;i++) 75 { 76 memset(cnt,0,sizeof(cnt)); 77 e[0]=i,c=1; 78 if(bfs()) 79 { 80 display(0); 81 t1=cnt[0]; 82 if(cmp())over(); 83 } 84 } 85 if(a1==0) 86 for(int i=1;i<k;i++) 87 { 88 for(int j=0;j<i;j++) 89 { 90 memset(cnt,0,sizeof(cnt)); 91 e[0]=j,e[1]=i,c=2; 92 if(bfs()) 93 { 94 display(0); 95 t1=cnt[0]; 96 if(cmp())over(); 97 } 98 } 99 } 100 for(int i=0;i<a1;i++)printf("%c",ans[i]); 101 printf(" "); 102 } 103 return 0; 104 }