找倍数
↑ 题目链接
题目
给定一个正整数 \(n\) ，请你找到一个它的非零倍数 \(m\) 。要求 \(m\) 中只包含数字 \(0\) 或 \(1\) ，并且总位数不超过 \(100\) 位。
输入格式
输入包含多组测试数据。
每组数据占一行，包含一个正整数 \(n\)
当输入 \(n=0\) 时，表示输入结束。
输出格式
每组数据输出一行 \(m\)
如果方案不唯一，则输出任意合理方案均可。
数据范围
\(1≤n≤200\)
输入样例：
2
6
19
0
输出样例：
10
100100100100100100
111111111111111111
思路
从 \(1\) 开始搜索，通过 \(BFS\) 向后每次扩展 \(0\) 和 \(1\) 两种情况 ，并且在乘法过程中不断取模，防止爆范围
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
while(cin>>n,n)
{
queue<pair<string,ll>>q;
q.push({"1",1ll});
while(q.size())
{
auto t=q.front();
q.pop();
if(t.second==0)//能被整除，输出答案
{
cout<<t.first<<endl;
break;
}
q.push({t.first+"0",(t.second*10)%n});//添0
q.push({t.first+"1",(t.second*10+1)%n});//添1
}
}
return 0;
}