POJ 1426 Find The Multiple bfs
题意:给你一个数n,让求一个只有0和1组成的十进制数x,x是n的倍数。
思路:bfs,因为只有0和1组成,所以最高位肯定是1,从1开始搜即可。搜索的过程中,若x%n已经出现过了,则不在入队。输出最先搜到的一个即可。
代码:
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
typedef long long LL;
int flag[210];
LL bfs(int n){
CLR(flag,0);
queue<LL> qq;
qq.push(1);
flag[1%n] = 1;
while(!qq.empty()){
LL x = qq.front();
if(x % n == 0)
return x;
qq.pop();
LL y = x * 10;
int yy = y % n;
LL z = x * 10 + 1;
int zz = z % n;
if(!flag[yy]){
qq.push(y);
flag[yy] = 1;
}
if(!flag[zz]){
qq.push(z);
flag[zz] = 1;
}
}
}
int main(){
//freopen("1.txt","r",stdin);
int n;
while(scanf("%d",&n) &&n){
LL ans = bfs(n);
printf("%lld\n",ans);
} www.zzzyk.com
return 0;
}
作者:wmn_wmn
补充:软件开发 , C++ ,