POJ 1426 Find The Multiple

【POJ】1426 Find The Multiple (BFS/DFS)

题目链接：poj-1426

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

---

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

---

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input

2
6
19
0

---

Sample Ouput

10
100100100100100100
111111111111111111

---

题目理解

​ 给定一个整数n，范围在[1,200],要求输出n的一个倍数，该倍数只能由0和1组成，输出任意一个即可。

​ 只能由0和1组成，那第一位肯定是1，后面的每一位都有两种可能。这就是在一个二叉树里面找都一个符合题意的数，如果使用BFS，那么找到的答案是最短的n的倍数，实测long long可以容纳，如果使用DFS，找到的答案必然比较长，需要使用数组了储存答案。

代码1 (BFS)

#include<iostream>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;

int n;
queue<LL> q;

LL BFS(int n){
	q.push(1);
	while(!q.empty()){
		LL front = q.front();
		q.pop();
		if(front % n == 0)
			return front;
		q.push(front * 10);		//在答案后面添加0
		q.push(front * 10 + 1);	//在答案后面添加1
	}
	return 0;
}

int main(){
	while(cin >> n && n){
		while(!q.empty())
			q.pop();
		cout << BFS(n) << endl;
	}

//测试数据是否会越界
//	for(int i = 1; i <= 200; ++i){
//		while(!q.empty())
//			q.pop();
//		cout << BFS(i) << endl;
//	}
	
	return 0;
}

---

代码2 (DFS)

#include<iostream>
#include<cstring>
using namespace std;

int n;
char ans[110];
bool flag;

void DFS(int divisor, int digit){
	if(digit > 100)
		return;
	if(divisor % n == 0){
		flag = true;
		ans[digit] = '\0';
		return;
	}
	if(!flag){  //flag用来判断是否已经找到答案
		ans[digit] = '0';
		DFS((divisor * 10) % n, digit + 1);
	}
	if(!flag){
		ans[digit] = '1';
		DFS((divisor * 10 + 1) % n, digit + 1);
	}
}

int main(){
	while(cin >> n && n){
		flag = false;
		memset(ans, '0', sizeof(ans));
		ans[0] = '1'; 
		DFS(1, 1);
		cout << ans << endl;
	}
	return 0;
}