poj1426（Find The Multiple）

题目来源：

来源poj1426

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 Output（输出不唯一）

10
100100100100100100
111111111111111111

代码

package poj;
import java.util.Scanner;
public class POJ1426_FindTheMultiple {
	static int n;
	static boolean flag;
	static long ans;
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		while(true){
			n = in.nextInt();
			if(n==0){
				break;
			}
			flag = true;
			ans = 1;
			dfs(n,ans,1);
		}
		in.close();
	}
	public static void dfs(int n, long ans, int deep){
		if(deep==20){
			return;
		}
		if(!flag){
			return;
		}
		if(ans % n == 0){
			System.out.println(ans);
			flag = false;
			return;
		}
		dfs(n, ans*10, deep+1);
		dfs(n, ans*10+1,deep+1);
		return;
	}
}