POJ 1426-Find The Multiple【搜索】

悠悠 2022-08-20 14:14 107阅读 0赞

Find The Multiple

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td colspan="3"><strong>Memory Limit:</strong> 10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 24187</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 10015</td> 
   <td>&nbsp;</td> 
   <td style="color:red; font-weight:bold">Special Judge</td> 
  </tr> 
 </tbody> 
</table>

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

解题思路：

long long 是可以过得。

#include<stdio.h>
    #include<queue>
    using namespace std;
    int n;
    
    void bfs(int d)
    {
    	queue<long long>q;
    	q.push(d);
    	while(!q.empty())
    	{
    		long long xx=q.front();
    		q.pop();
    		if(xx%n==0)
    		{
    			printf("%lld\n",xx);
    			return;
    		}	
    		q.push(xx*10);
    		q.push(xx*10+1);
    	}
    }
    int main()
    {
    
    	while(scanf("%d",&n)!=EOF)
    	{
    		if(n==0)
    		break;
    		bfs(1);
    	}
    	return 0;
    }