Description

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

Input

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

Output

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

Sample Input

2
6
19
0

Sample Output

10
100100100100100100
111111111111111111

Translation

输入一个不大于200200的正整数nn，输出一个nn的倍数，且这个倍数只能由00和11构成。

Idea

逐项检验肯定是不行的，我们不妨想想怎么构造0101串。
要使构造的0101串xx成为nn的倍数，那么最小的xx就是11，之后就是10,11,100,101,110,111...10,11,100,101,110,111...
可见，对于任何一个0101串xx，都可延伸出两个0101串10x+1,10x10x+1,10x，就这样从11开始，形成了一颗无限的完全二叉树，这样的数据结构，适合BFSBFS构造。
于是可以枚举[1,200][1,200]之间的全部整数，找到它们符合条件的倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<vector>
#include<queue>
#define ull unsigned long long 
using namespace std;
const int N=200;
vector<ull>ans;
void init()
{
	int i;
	queue<ull>multiple;
	for(i=1;i<=N;i++)
	{
		//初始化，清空队列
		queue<ull>e;
		swap(e,multiple);
		//从1开始递推
		multiple.push(1);
		while(!multiple.empty())
		{
			ull now=multiple.front();
			if(now%i==0) 
			{
				//找到倍数，退出循环
				ans.push_back(now);
				break;
			}
			else
			{
				//根节点出队
				multiple.pop();
				//两个子节点入队
				multiple.push(now*10);
				multiple.push(now*10+1);
			}
		}
	}
}
int main()
{
	init();
	int i;
	for(i=1;i<=200;i++) printf("%d*%lld=%lld\n",i,ans[i-1]/i,ans[i-1]);
	return 0;
}

打了个表出来（以下未显示全部），但是这样之解写进程序会MLE，因此把这一堆数据复制到数组里输出吧。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
using namespace std;
//打表
unsigned long long ans[]={
1,10,111,100,10,1110,1001,1000,
111111111,10,11,11100,1001,10010,
1110,10000,11101,1111111110,11001,
100,10101,110,110101,111000,100,
10010,1101111111,100100,1101101,
1110,111011,100000,111111,111010,
10010,11111111100,111,110010,10101,
1000,11111,101010,1101101,1100,
1111111110,1101010,10011,1110000,
1100001,100,100011,100100,100011,
11011111110,110,1001000,11001,11011010,
11011111,11100,100101,1110110,1111011111,
1000000,10010,1111110,1101011,1110100,
10000101,10010,10011,111111111000,10001,
1110,11100,1100100,1001,101010,10010011,
10000,1111111101,111110,101011,1010100,
111010,11011010,11010111,11000,11010101,
1111111110,1001,11010100,10000011,100110,
110010,11100000,11100001,11000010,
111111111111111111,100,101,1000110,
11100001,1001000,101010,1000110,100010011,
110111111100,1001010111,110,111,10010000,1011011,
110010,1101010,110110100,10101111111,110111110,
100111011,111000,11011,1001010,10001100111,
11101100,1000,11110111110,11010011,10000000,
100100001,10010,101001,11111100,11101111,
11010110,11011111110,11101000,10001,100001010,
110110101,100100,10011,100110,1001,1111111110000,
11011010,100010,1100001,11100,110111,11100,
1110001,11001000,10111110111,10010,1110110,
1010100,10101101011,100100110,100011,100000,
11101111,11111111010,1010111,1111100,1111110,
1010110,11111011,10101000,10111101,111010,
1111011111,110110100,1011001101,110101110,
100100,110000,100101111,110101010,11010111,
11111111100,1001111,10010,100101,110101000,
1110,100000110,1001011,1001100,1010111010111,
110010,11101111,111000000,11001,111000010,101010,
110000100,1101000101,1111111111111111110,
111000011,1000
};
int main()
{
	int n;
	while(cin>>n&&n) cout<<ans[n-1]<<endl;
	return 0;
}