使用广搜，每一位都是0~k-1的数，使用广搜去每一层遍历每一位
在搜索过程中会出现位数很大的数字，所以使用字符串去拼接保存，但每变化一次都要记录相应字符串的余数，在这里使用余数分配率进行计算。
在使用一个vis数组去记录哪些余数已经出现过了，因为如果余数已经出现过了那么根据取余运算的分配率这个数就没有意义了，直接剪枝。 
//使用广搜，每一位都是0~k-1的数，使用广搜去每一层遍历每一位
//在搜索过程中会出现位数很大的数字，所以使用字符串去拼接保存，但每变化一次都要记录相应字符串的余数，在这里使用余数分配率进行计算。
//在使用一个vis数组去记录哪些余数已经出现过了，因为如果余数已经出现过了那么根据取余运算的分配率这个数就没有意义了，直接剪枝。

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1000+10;
struct Node {
    string s;
    int yu;
};
queue<Node> q;
int k, m;
int vis[maxn];

string BFS(string s) {
    vis[s[0]-'0'] = 1;
    q.push({s, (s[0]-'0')%m});
    while (!q.empty()) {
        Node p = q.front();
        if (p.yu==0) return p.s;
        q.pop();
        for (int i=0;i<k;i++) {
            int newyu = (((p.yu%m)*(10%m))%m+i%m)%m;
            if (!vis[newyu]) {
                vis[newyu] = 1;
                string news = p.s + to_string(i);
                q.push({news, newyu});
            }
        }
    }
    return "0";
}

int main() {
    cin>>k>>m;
    string as;
    bool flag = true;
    for (int i=1;i<k;i++) {
        while (!q.empty()) q.pop();
        memset(vis, 0, sizeof(vis));
        string ans = BFS(to_string(i));
        if (ans!="0") {
            if (flag)
                as = ans;
            as = as.length()>ans.length()? ans:as;
            flag = false;
        }
    }
    cout<<as;
    return 0;
}