Multiple
| Time Limit: 1000MS | Memory Limit: 32768K | |
| Total Submissions: 5423 | Accepted: 1179 |
Description
a program that, given a natural number N between 0 and 4999 (inclusively), and M distinct decimal digits X1,X2..XM (at least one), finds the smallest strictly positive multiple
of N that has no other digits besides X1,X2..XM (if such a multiple exists).
of N that has no other digits besides X1,X2..XM (if such a multiple exists).
Input
The input has several data sets separated by an empty line, each data set having the following format:
On the first line - the number N
On the second line - the number M
On the following M lines - the digits X1,X2..XM.
Output
For each data set, the program should write to standard output on a single line the multiple, if such a multiple exists, and 0 otherwise.
An example of input and output:
Sample Input
22
3
7
0
1
2
1
1
Sample Output
110
0
一道比较经典的BFS，剪纸策略真的很强大，值得学习！！
剪枝策略：
若A=n*i+r
B=n*j+r
即A和B同余（i<j)，那么若A*10+d[k]能被n整除，那么B*10+d[k]也能被n整除（其中d[k]表示允许出现的一个数字），所以此处就可以做个剪枝了，对于余数相同的数取其最小的。
ps：由于最后的结果可能会很大，所以我在每个状态节点中记录了前一个状态，而且在每个状态中记录当前状态是由哪个数字得到的。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct st
{
int pre;//前一个状态
int r;//余数
int d;//个位数
}w,v;
st q[5000];
int num[10];//数字
bool visit[5000];
int n,m;
void output(int i)
{
if(q[i].pre==-1)
return;
output(q[i].pre);
printf("%d",q[i].d);
}
void bfs()
{
if(n==0)
{
printf("0\n");
return;
}
int front,rear;
bool ok;
front=rear=0;
w.pre=-1;
w.d=0;
w.r=0;
q[rear++]=w;
visit[0]=true;
ok=false;
while(front<rear)
{
w=q[front++];
for(int i=0;i<m;i++)
{
int r=w.r*10+num[i];
if(r>=n&&r%n==0)
{
output(front-1);
printf("%d\n",num[i]);
ok=true;
break;
}
r%=n;
if(!visit[r])
{
visit[r]=true;
v.r=r;
v.pre=front-1;
v.d=num[i];
q[rear++]=v;
}
}
if(ok)
break;
}
if(!ok)
printf("0\n");
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<n;i++)
visit[i]=false;
for(int i=0;i<m;i++)
scanf("%d",num+i);
sort(num,num+m);//由小到大排序
bfs();
}
return 0;
}