给定一个自然数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;
}