描述
题解
这里只强调了M>0
,而没有提其上限,那么只有一种可能,就是M
极大,会远远超出long long
,所以我们这里需要用到BFS
求出其最小的M
,但是需要输出M
,所以需要结合DFS
输出。
这里可以进行一下剪枝,定义一个vis
数组用来存储余数状态,如果某一个余数出现过了,那么第二次出现时可以直接剪去,因为当一个余数出现了两次,说明这种前缀延伸出来的结果无意义(不是最小的M
)。
代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 5e6;
struct node
{
int x;
int per;
} ans[MAXN];
bool vis[MAXN]; // 表示余数状态0表示未出现过,1表示出现过
int n, num;
void DFS(int pos)
{
int res = ans[pos].per;
if (res <= 0)
{
printf("1");
return;
}
DFS(res);
printf("%d", ans[res].x);
return ;
}
void BFS()
{
num = 1;
memset(vis, 0, sizeof(vis));
node cur, tmp;
cur.x = 1, cur.per = 0;
queue<node> q;
ans[0].x = 1;
ans[0].per = 0;
q.push(cur); // M>0
while (!q.empty())
{
tmp = q.front();
q.pop();
for (int i = 0; i <= 1; i++)
{
cur.x = tmp.x * 10 + i;
cur.x %= n; // 表示余数
if (!vis[cur.x]) // 剪枝,如果前边已经出现过cur.x,剪去这种情况
{
cur.per = num;
vis[cur.x] = 1; // 标记
ans[num].x = i;
ans[num].per = tmp.per;
q.push(cur);
if (cur.x == 0)
{
DFS(num);
printf("%d\n", i);
return;
}
num++;
}
}
}
}
int main()
{
while (scanf("%d", &n) != EOF)
{
if (n == 1)
{
printf("1\n");
continue;
}
BFS();
}
return 0;
}