学步园

给你一个数n，在不能用某些数字的情况下找到能表示成n的倍数的最小值，如果不能表示输出-1。

首先模运算的规则：

A % N == B % N  → A*K % N == B*K % N → (A + C) % N == (B + C) % N → (A*K + C) % N == (B*K + C)
% N

→ (A*10 + C) % N == (B*10 + C) % N

所以可以用bfs搜索，从数字最小的情况搜起。每次只需保存余数，和最先出现这个余数时，记录添加在末尾的那位数字，一旦遇到余数为0，则将记录中的数字逆序输出。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>

using namespace std;

const int maxn = 10010;
int n, m, x;
bool dig[10];
int pre[maxn], save[maxn];
queue<int> q;

void put(int u)
{
        if(pre[u] != -1)
                put(pre[u]);
        printf("%d", save[u]);
}

void bfs()
{
        while(!q.empty())
                q.pop();
        int rema, now;
        for(int i = 1; i <= 9; i++)
        {
                if(!dig[i])
                {
                        rema = i % n;
                        if(rema == 0)
                        {
                                printf("%d", i);
                                return ;
                        }
                        q.push(rema);
                        save[rema] = i;
                }
        }
        while(!q.empty())
        {
                now = q.front();
                q.pop();
                for(int i = 0; i <= 9; i++)
                {
                        if(!dig[i])
                        {
                                rema = (now * 10 + i) % n;
                                if(save[rema] == -1)
                                {
                                        q.push(rema);
                                        pre[rema] = now;
                                        save[rema] = i;
                                }
                                if(rema == 0)
                                {
                                        put(rema);
                                        return ;
                                }
                        }
                }
        }
        printf("-1");
}

int main()
{
        int cas = 0;
        while(~scanf("%d%d", &n, &m))
        {
                printf("Case %d: ", ++cas);
                memset(dig, false, sizeof(dig));
                memset(pre, -1, sizeof(pre));
                memset(save, -1, sizeof(save));
                for(int i = 0; i < m; i++)
                {
                        scanf("%d", &x);
                        dig[x] = true;
                }
                bfs();
                printf("\n");
        }
        return 0;
}