$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个正整数 $n$,请你找到一个它的非零倍数 $m$。
要求 $m$ 中只包含数字 $0$ 或 $1$,并且总位数不超过 $100$ 位。
输入格式
输入包含多组测试数据。
每组数据占一行,包含一个正整数 $n$。
当输入 $n=0$ 时,表示输入结束。
输出格式
每组数据输出一行 $m$。
如果方案不唯一,则输出任意合理方案均可。
数据范围
$1 \\le n \\le 200$
输入样例:
2
6
19
0
输出样例:
10
100100100100100100
111111111111111111
思路
- bfs的思想,初始让$1$放入队列,每次取出队头$x$,判断是否满足$x%n==0$,不满足将$10\times x$和$10 \times x+1$放入队列中.
- 类似于
二叉树
的枚举方式,由于在计算时不考虑前导$0$,可看作是以$1$为根,左子树填$10$,右子树填$11$的二叉树
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
int n;
ll bfs()
{
queue<ll> q;
q.push(1);
while(q.size()>0)
{
ll temp=q.front();
q.pop();
if(temp%n==0)
return temp;
q.push(temp*10);
q.push(temp*10+1);
}
return -1;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
printf("%lld\n",bfs());
}
return 0;
}
数据太大longlong不会爆的吗?
由于n小于200,结果最大1111111111111111110能用long long 保存
大佬为什么n小于200,结果最大就是1111111111111111110呢,谢谢解答
通过打表的方式打出来的,没超过long long的存储范围
好的谢谢