Find The Multiple-蒲公英云

Find The Multiple

亦凉 2022-08-07 09:51 259阅读 0赞

Find The Multiple
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u
Submit

Status

Practice

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 Output
10
100100100100100100

111111111111111111

#include <cstdio>
#include <queue>
using namespace std;
__int64 a[205];
void bfs(int n)
{
    __int64 k;
    queue<__int64>Q;
    Q.push(1);
    while( !Q.empty() ){
        k=Q.front(); Q.pop();
        if(k%n==0)  { a[n]=k; return; }
        Q.push(k*10);
        Q.push(k*10+1);
    }
}
void get_a()
{
    a[0]=0; a[1]=1; a[2]=10;
    for(int i=3; i<=200; i++){
        if(i%2==0) a[i]=a[i/2]*10;
        else bfs(i);
    }
}
int main()
{
    int n;
    get_a();
    while(scanf("%d", &n)!=-1 && n!=0){
        printf("%I64d\n", a[n]);
    }
    return 0;
}