- // 题意 求 n 的倍数 且只含有 01 的数
- // 同余定理 + bfs
- //#include<bits/stdc++.h>
- #include<queue>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<iostream>
- using namespace std;
- const int N = 1e6+4;
- int mod[N];
- // 题意 求 n 的倍数 且只含有 01 的数
- // 同余定理 + bfs
- int main(){
- int n;
- while(cin>>n &&n){
- mod[1] = 1%n;
- int las = 1;
- int i;
- // 就是把 通过 i/2 得到的上一位, 然后分别 + 0,+1 位 用 i 二进制表示 n
- for(i=2;mod[i-1]!=0;i++) // 利用同余模定理, 从前一步的余数 mod[i/2] 得到下一步的余数 mod[i]
- mod[i]=(mod[i/2]*10+i%2)%n;
- //mod[i/2]*10+i%2 模拟了 BFS 的双入口搜索
- // 当 i 为偶数时,+0, 即取当前位数字为 0 . 为奇数时, 则 + 1, 即取当前位数字为 1
- las = i-1;
- // cout<<las<<endl;
- int ans[222];int len =0;
- while(las){
- ans[len++] = las%2;
- las/=2;
- }
- for(int i=len-1;i>=0;--i)
- printf("%d",ans[i]);
- cout<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2944504.html