本文最后更新于 811 天前,其中的信息可能已经有所发展或是发生改变。
给定一个正整数 n,请你找到一个它的非零倍数 m。
要求 m 中只包含数字 0 或 1,并且总位数不超过 100 位。
输入格式
输入包含多组测试数据。
每组数据占一行,包含一个正整数 n。
当输入 n=0 时,表示输入结束。
输出格式
每组数据输出一行 m。
如果方案不唯一,则输出任意合理方案均可。
数据范围
1≤n≤200
输入样例:
输出样例:
2
6
19
0
输出样例:
10
100100100100100100
111111111111111111
分析
- 难点在于取模注意:
11 % 2 = ((1 × 10) % 2 + 1) % 2
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
queue<pair<string,ll>> ans; //存储答案
int main()
{
while(cin>>n&&n){
while(ans.size()) ans.pop(); //清空数据
ans.push({"1",1}); //将1入队,作为队头扩展搜索
while(!ans.empty()){
auto p=ans.front();
ans.pop();
if(p.second==0){ //满足条件输出,
cout<<p.first<<endl;
break;
}
ans.push({p.first+"0",(p.second*10)%n}); //末尾补零入队,并对其取模
ans.push({p.first+"1",(p.second*10+1)%n}); //末尾补1入队,并对其取模
}
}
return 0;
}