学步园

解题方法

BFS     且要知道 (a + b) % n == ( (a%n) + (b%n) ) % n

我们可以从左到右构造目标数字 目标数字肯定是以 1 开头的 接下来可以是 0 也可以是 1 我们可以用BFS来枚举

我们开一个标记数组 vis[i], vis[i] == true 表示 我们已经枚举过一个数 这个数 mod n 等于 i, 可以用一个map<int,LL>M 来保存这个枚举的数 即 M[i]

因为如果 某个数 x % n == y 的话 再遇到 % n == y的数的话 这个数和 x 是等价的 因为前面部分 % n == y 后面部分如果两个都往下枚举的话 mod n肯定也是相等的 

当我们枚举到一个数 这个数 mod n == 0的话即表示这个数是合法的

测试发现要用 long long 才能保存下某些输入数据的答案

参考代码 - 有疑问的地方在下方留言 看到会尽快回复的

#include <iostream>
#include  <cstdio>
#include <queue>
#include <cstring>
#include <map>

using namespace std;

typedef long long LL;

bool vis[300];

LL BFS(int n) {
	queue<int>q;
	memset(vis, 0, sizeof(vis));
	map<int,LL>M;
	M[1] = 1;
	vis[1] = 1;
	LL ans = -1;
	q.push(1);
	while(!q.empty()) {
		int f = q.front();
		//printf("f = %d %lld\n", f, M[f]);
		if(f % n == 0) return M[f];
		q.pop();
		int tmp = f * 10 % n;
		if(!vis[tmp]) {
			vis[tmp] = true;
			M[tmp] = M[f] * 10;
			q.push(tmp);
		}
		tmp = (f * 10 + 1) % n;
		if(!vis[tmp]) {
			vis[tmp] = true;
			M[tmp] = M[f] * 10 + 1;
			q.push(tmp);
		}
	}
	return ans;
}

int main() {
	int n;
	while(scanf("%d", &n), n) {
		LL ans = BFS(n);
		cout<<ans<<endl;
	}
	return 0;
}