POJ1426 - Find The Multiple

Task

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:

output:

1
2
3


10
100100100100100100
111111111111111111

Solution

本题很多人上来就用unsigned long long来表示最终结果来BFS，虽然本题测试样例很简单导致结果不会超出ull的范围（18位十进制数），但本文假设了结果最多是100位十进制数，远远超出了ull的范围，最好另找正经解法。最简单的思路，可在节点中存储0/1字符串来表示大数，再存储一个整型余数。这是一个二叉树的BFS，左右子节点分别对应字符串末尾加0或1。但因为一层节点太多，都放进队列时会memory limit和time limit交替进行。此法不妥。

1、为了缩短计算时间，首先认识到：结果由0和1组成，可以写为10的幂之和，即 \begin{equation} \left(\sum_{<i>}10^i\right)\%n=0 \quad \Rightarrow \quad \left(\sum_{<i>}(10^i\%n)\right)\%n=0 \end{equation}所以可用数组存储10的各次幂对n的余数，需要时直接查找，不用计算。这个数组可由一次递归求出，即已知x%n，可求(x*10)%n： \begin{equation} (x\cdot 10)\%n=\left((x\%n)\cdot(10\%n)\right)\%n \end{equation}因此可由1%n得到所有10的幂的余数，它们组成一个序列rmd_pow10，长度最大为最长位数MAX_LEN_RMD=100。

2、为了缩小搜索空间，需要从低位往高位搜索。如果从低到高搜，搜过两个数x和y，它们对n同余，则x和y对应的子树在同余上是是等价的，在x前面放任意0/1序列，在y前面放同样的0/1序列，得到的结果对n仍同余。即 \begin{equation} x\%n=y\%n \quad \Rightarrow \quad \forall z:(z\cdot x)\%n=(z\cdot y)\%n \end{equation}因此对每个节点存储一个余数，如果搜索其他节点时碰到同样余数，就可以认为两个节点的子树等价，因此不需要再搜索这个新节点了，大幅减小搜索空间。因此可做一个bool型序列visited，标记一个余数有没有被访问过。该序列位置编码余数，对应位置为1表示已经被访问过。最大长度为n的最大值MAX_LEN_VISIT=200。

如图所示（每个节点的第一个元素不准确，应该还要变换到[1,n]），由于是从低位开始遍历，故节点中存储的字符串要反过来才是结果。每个节点的左子节点和自己相同，因为只是在最前面加了个0。也因为这个原因，左子节点不能像上面说的那样按照重复子树处理，否则递归不能继续。而左子节点一定不会是最终结果，因为是0开头的数字。右子节点才是真正有可能产生最终结果的，而且可以按照重复子树优化掉很多。例如，n=7时，‘01’的子树和‘101’的子树是重复的，因为10%7=101%7=3，所以两者在头部加上任何数，对7的模都是相同的。可认为‘101’的子树重复。 BFS

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX_LEN_RMD 100
#define MAX_LEN_VISIT 200
int n;
int rmd_pow10[MAX_LEN_RMD];
bool visited[MAX_LEN_VISIT];
struct node{
    int rem;
    int depth;
    string result;
    node(int r,int d, const string &s): rem(r), depth(d), result(s) {}
};
string BFS(){
    // q must be declared in this function. 
    // if q was declared as global var, 
    // time limit will be exceeded. 
    queue<node> q;
    node node0=node(n,0,"");
    q.push(node0);
    while(!q.empty()){
        node node1=q.front();
        q.pop();
        if(node1.rem==0)
            return node1.result;
        // result is power of 10
        if(rmd_pow10[node1.depth]==0){
            string ret(node1.depth+1,'0');
            ret[node1.depth]='1';
            return ret;
        }
        // left, cannot be result
        int rem_l=node1.rem;
        int depth_l=node1.depth+1;
        if(depth_l<MAX_LEN_RMD){
            visited[rem_l]=1;
            node node_l=node(rem_l,depth_l,node1.result+"0");
            q.push(node_l);
        }
        // right
        int rem_r=node1.rem-rmd_pow10[node1.depth];
        if(rem_r<0)
            rem_r+=n;
        int depth_r=node1.depth+1;
        // cut many subtrees with visited
        if(visited[rem_r]==0 && depth_r<MAX_LEN_RMD){
            visited[rem_r]=1;
            node node_r=node(rem_r,depth_r,node1.result+"1");
            q.push(node_r);
        }
    }
    return "deliaf";
}
int main(){
    while(scanf("%d",&n)!=EOF && n!=0){
        memset(visited,0,sizeof(bool)*MAX_LEN_VISIT);
        int c=10%n;
        rmd_pow10[0]=1;
        for(int i=1; i<MAX_LEN_RMD; ++i)
            rmd_pow10[i]=(rmd_pow10[i-1]*c)%n;
        string result=BFS();
        reverse(result.begin(),result.end());
        printf("%s\n",result.c_str());
    }
    return 0;
}

文章目录

Task

Input

Output

Sample

Solution