C++(g++ 7.5.0) 解法, 执行用时: 129ms, 内存消耗: 27680K, 提交时间: 2023-02-10 10:28:33

#include<bits/stdc++.h>
using namespace std;
int n,m;
string a="0123456789";
typedef struct Node{
    string x;
    int mod;
}node;
queue<node> qe;
map<int,int> mp;
string bfs()
{
    string t="1";
    for(int i=1;i<n;i++){
       t[0]=i+'0';
        qe.push({t,i});
    }
    while(!qe.empty())
    {
        node k=qe.front();
        qe.pop();
        mp[k.mod]=1;
        for(int i=0;i<n;i++){
            int temp=a[i]-'0';
            temp=(k.mod*10+temp)%m;
            if(mp[temp]!=0)continue;
            if(temp==0)return k.x+a[i];
            qe.push({k.x+a[i],temp});
        }
    }
    return "";
}
int main()
{
    cin>>n>>m;
    cout<<bfs();
}

pypy3 解法, 执行用时: 125ms, 内存消耗: 26452K, 提交时间: 2023-05-24 16:19:21

import collections

k, m = map(int, input().split())
vis = [0]*m
q = collections.deque()

def bfs():
    for i in range(1, k):
        step = []
        step.append(str(i))
        step.append(i%m)
        vis[i%m] = 1
        q.append(step)
        
#     print(q)
        
    while q:
        p = q.popleft()
#         print(p)
        if p[1]==0:
            return p[0]
        for i in range(k):
            y = (p[1]*10+i)%m
            if not vis[y]:
                q.append([p[0]+str(i), y])
                vis[y] = 1
#         print(q, vis)
                
    return -1

print(bfs())

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 416K, 提交时间: 2022-08-24 21:35:31

#include <bits/stdc++.h>
using namespace std;

struct node{
	string str;
	int mod;
};

string bfs(int k, int m){
	queue<node> q;
	map<int, int> mp;
	for(int i = 1; i < k; i++)
		q.push({to_string(i), i % m});
		
	while(!q.empty()){
		node f(q.front()); q.pop();
		mp[f.mod] = 1;
		if(f.mod == 0)return f.str;
		for(int i = 0; i < k; i++){
            int t = f.mod * 10 + i;
			if(mp.count(t % m))continue;
			mp[t % m] = 1;
			q.push({f.str + char(i + '0'), t % m});
		}
	}
	return "";
}

int main(){
	int k, m;
	cin >> k >> m;
	cout << bfs(k, m) << endl;
	return 0;
}