1136.cpp

给出数n和m(m<9)个数字,求只含有m个数字的n的最小倍数.

//适用整数位数小于20位的，1136的答案超过400位（吓人）
#include<iostream.h>
#include<stdlib.h>


int dig[10],n,m,number_i;
bool data[4999];
struct node
{
int number[2];
short pre;
};
node a[10000];

int  cmp( const void *a, const void *b) 
{ 
   int s=*(int*)a,t=*(int*)b; 
   return s-t;  
}

int bfs()
{
bool flag = true;
int first,last,j,first1;
short k,re,mod_number;
re = n - 1;
number_i = 0;
if(dig[0] != 0)
{
a[0].number[0] = dig[0];
mod_number = dig[0] % n;
if(mod_number == 0)
  return 0;
a[0].pre = mod_number; 
data[mod_number] = true;
re--; 
}
number_i++;

for(j = 1;j < m;j++)
{
a[j].number[0] = dig[j];
mod_number = dig[j] % n;
if(mod_number == 0)
  return (j);
if(data[mod_number] == true)
  continue;    
a[j].pre = mod_number; 
data[mod_number] = true;
re--; 
}

if(dig[0] == 0)
  first = 1;
else  first = 0;
last = m ;

while(flag)
{
number_i++;
flag = false;
first1 = last;
for(j = first;j < last;j++)
{
for(k = 0;k < m;k++)
{

if(number_i < 10)
{                           // if if if 

mod_number = (a[j].pre*10 + dig[k]) % n;
if(mod_number == 0)
{ 
	a[first1].number[0] = a[j].number[0]*10 + dig[k];
    return (first1);
}
    else {
    if(data[mod_number] == true )
      continue;
      else {  data[mod_number] = true;
              a[first1].number[0] = a[j].number[0]*10 + dig[k];
              a[first1].pre = mod_number;
              first1++;
              re--;
              if(re == 0) return -1;
              flag = true;
      }
    }  //end if 

} // if if if
else  if(number_i == 10){     // else else
	mod_number = (a[j].pre*10 + dig[k]) % n;
if(mod_number == 0)
{ 
	a[first1].number[1] = dig[k];
    a[first1].number[0] = a[j].number[0];
    return (first1);
}
    else {
    if(data[mod_number] == true )
      continue;
      else {  data[mod_number] = true;
              a[first1].number[1] = dig[k];
              a[first1].number[0] = a[j].number[0];
              a[first1].pre = mod_number;
              first1++;
              re--;
              if(re == 0) return -1;
              flag = true;
      }
    }  


}                                          //  else else
else {   mod_number = (a[j].pre*10 + dig[k]) % n;
if(mod_number == 0)
{ 
	a[first1].number[1] = a[j].number[1]*10 + dig[k];
    a[first1].number[0] = a[j].number[0];
    return (first1);
}
    else {
    if(data[mod_number] == true )
      continue;
      else {  data[mod_number] = true;
              a[first1].number[1] = a[j].number[1]*10 + dig[k];
              a[first1].number[0] = a[j].number[0];
              a[first1].pre = mod_number;
              first1++;
              re--;
              if(re == 0) return -1;
              flag = true;
      }
    }  

}

}  //end k
}  // end j
first = last;
last = first1;
}  //end while

return -1;
}


int main()
{
int i,numth;
while(cin>>n)
{
for(i = 0;i < n;i++)
   data[i] = false;
cin>>m;
for(i = 0;i < m;i++)
  cin>>dig[i];
if(n==0) 
      { 
         cout<<"0"<<endl; 
         continue; 
      } 
qsort(dig,m,sizeof(int),cmp); 

numth = bfs();
if(numth == -1)
cout<<"0"<<endl;
else if(number_i < 10)
cout<<a[numth].number[0]<<endl;
else cout<<a[numth].number[0]<<a[numth].number[1]<<endl;
}
return 0;
}