自动搬运

查看原文

来自洛谷，原作者为

	吾王美如画 烦诶

搬运于2025-08-24 21:26:58，当前版本为作者最后更新于2019-08-10 16:10:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

唔姆

（隔了好久没写过题解，可能不会写了23333）

• 首先看问题，利用0～k-1这k个数构成最小的可以整除m的数
• 接着我们就想到了暴搜，使用bfs每次往现有的数字后加一位，因为dfs的性质，所以最先找到的数一定是最小的。（显然这样是过不了的
• 但是我们可以发现 a$\equiv$b(mod m)，那么显然a×10+c$\equiv$b×10+c(mod m)。而我们又只需要最小的答案，所以当一个数的模数曾经出现过，我们就不需要这个数了。

根据上文我们得到这样一个代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int k,m;
int mod[15000];
queue<long long>q;
long long bfs(){
	while(!q.empty()){
		long long now=q.front();
		q.pop();
		for(int i=0;i<k;i++){
			long long to=now*10+i;
			if (mod[to%m]==0){
				mod[to%m]=1;
				q.push(to);
				if (to%m==0)return to;
			}
		}
	}
}
int main(){
	cin>>k>>m;
	for(int i=1;i<k;i++){
		q.push(i);
		mod[i%m]=1;
	}
	if (k==2&&m==999)printf("111111111111111111111111111");
	else cout<<bfs();
	return 0;
} 

因为最后一个点超大，所以longlong也会爆。（我看好多人都这样直接打表过的

所以我们进一步想，由之前提到的a$\equiv$b(mod m)而a×10+c$\equiv$b×10+c(mod m)，我们没有必要把整个数放入队列，只需放对m的模数就ok，最后为了输出，保存每个数的father和这时选的是哪个数，反向输出就OK。

（代码完全体

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int k,m;
int mod[15000],fa[15000],which[15000];
queue<int>q;
void out(int now){
    if (now==-1)return;
    out(fa[now]);
    cout<<which[now];
}
void bfs(){
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<k;i++){
			int to=(now*10+i)%m;
			if (mod[to]==0){
				mod[to]=1;
                which[to]=i;
                fa[to]=now;
				q.push(to);
				if (to==0){
                    out(to);
                    return;
                }
			}
		}
	}
}
int main(){
	cin>>k>>m;
    memset(fa,-1,sizeof(fa));
	for(int i=1;i<k;i++){
		q.push(i%m);
		mod[i%m]=1;
        which[i%m]=i;

	}
	bfs();
	return 0;
}