POJ 1426 Find The Multiple
Description
Given a positive integer , write a program to find out a nonzero multiple m of whose decimal representation contains only the digits and . You may assume that is not greater than 200 and there is a corresponding m containing no more than decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of . A line containing a zero terminates the input.
Output
For each value of in the input print a line containing the corresponding value of . The decimal representation of must not contain more than digits. If there are multiple solutions for a given value of , any one of them is acceptable.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111
Translation
输入一个不大于的正整数,输出一个的倍数,且这个倍数只能由和构成。
Idea
逐项检验肯定是不行的,我们不妨想想怎么构造串。
要使构造的串成为的倍数,那么最小的就是,之后就是
可见,对于任何一个串,都可延伸出两个串,就这样从开始,形成了一颗无限的完全二叉树,这样的数据结构,适合构造。
于是可以枚举之间的全部整数,找到它们符合条件的倍数。
1 |
|
打了个表出来(以下未显示全部),但是这样之解写进程序会MLE,因此把这一堆数据复制到数组里输出吧。
Code
1 |
|