01組成的N的倍數

給定一個自然數N，找出一個M，使得M > 0且M是N的倍數，并且M的10進制表示隻包含0或1。求最小的M。

例如：N = 4，M = 100。

Input

輸入1個數N。(1 <= N <= 10^6)
           

Output

輸出符合條件的最小的M。
           

Input示例

4
           

Output示例

100
           

思路：

bfs。因為每一位隻能是0或1，将第一位設為1，然後一次對0和1進行bfs。需要記錄餘數是否已經出現過。

​#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>
#include <stdio.h>
using namespace std;

const int MAXN = 1e6 + 5;
struct Node
{
	int val;
	int r;
	int prev;
};

Node buf[2*MAXN];
bool used[2*MAXN];
int n;

void output(int k)
{
	if (buf[k].prev != -1)
	{
		output(buf[k].prev);
	}

	cout << buf[k].val;
}

int main()
{
	cin >> n;
	if (n == 1)
	{
		cout << 1 << endl;
		return 0;
	}

	buf[0].val = 1;
	buf[0].r = 1;
	buf[0].prev = -1;
	int len = 1;
	bool found = false;
	memset(used, false, sizeof(used));

	for (int i = 0; i < MAXN; i++)
	{
		found = false;
		for (int j = 0; j < 2; j++)
		{
			int temp = (buf[i].r * 10 + j) % n;
			if (!used[temp])
			{
				buf[len].val = j;
				buf[len].r = temp;
				buf[len].prev = i;
				used[temp] = true;
				len++;
			}
			if (temp == 0)
			{
				found = true;
				break;
			}
		}
		if (found)
		{
			break;
		}
	}

	output(len - 1);
	cout << endl;

    return 0;
}
​