poj1426

Find The Multiple

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 10685		Accepted: 4404		Special Judge

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

Sample Output

10
100100100100100100
111111111111111111

没有仔细分析题目，我一看最后的output不会超过100位，我就在想怎么存呢

想了好久也没想出好方法，如果数组存的话，可能会超内存，判断也可能会超时，最后现不到好办法

我还想要不要用double存，然后只是判断麻烦一些而以，

结果去网上找题解发现，只要longlong就能出正解

呃……我是沙茶

还有队列开了好大，要定义成全局变量

 1#include<stdio.h>
 2#include<string.h>
 3#include<math.h>
 4int n;
 5long long now,q[1000000];
 6void bfs()
 7{
 8    int head,tail;
 9    head=0;
10    tail=1;
11    q[tail]=1;
12    while(head<tail)
13    {
14        head++;
15        now=q[head];
16        now=now*10;
17        if(now%n==0)
18        {
19            break;
20        }
21        tail++;
22        q[tail]=now;
23        tail++;
24        q[tail]=now+1;
25    }
26    printf("%I64d\n",now);
27}
28int main()
29{
30    while(scanf("%d",&n)!=EOF&&n!=0)
31    {
32        bfs();
33    }
34    return 0;
35}
36