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).
The input file 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.
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:
Input
22
3
7
0
1
2
1
1
Output
110
0
题意：让你用m个数组成n的倍数，要求最小
思路：首先我们排序这m个数，然后从高位开始搜，这样才能保证最先BFS的是最小的，这里用到了一个剪枝就是对于：余数相同的，我们可以拿来判重，小的比较优，也就是最先放进队列的比较优
#include
#include
#include
#include
#include
using namespace std; const int maxn = 10005; struct Node { int res; int pre; int digit; } q[maxn]; int a[maxn], vis[maxn]; int n, m; void print(int u) { if (q[u].pre == -1) return; print(q[u].pre); printf("%d", q[u].digit); } int bfs() { q[0].digit = 0; q[0].pre = -1; q[0].res = 0; memset(vis, 0, sizeof(vis)); int front = 0, rear = 1; while (front < rear) { Node tmp = q[front]; for (int i = 0; i < m; i++) { int t = (tmp.res * 10 + a[i]) % n; if (a[i] == 0 && tmp.pre == -1) continue; if (!vis[t]) { vis[t] = 1; Node tmp; tmp.digit = a[i]; tmp.pre = front; tmp.res = t; q[rear++] = tmp; } if (t == 0) { print(rear-1); printf("\n"); return 1; } } front++; } return 0; } int main() { while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i < m; i++) scanf("%d", &a[i]); if (n == 0) { printf("0\n"); continue; } sort(a, a+m); if (!bfs()) printf("0\n"); } return 0; }