// 596K 32MS    G++
#include <cstdio>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define MAX1 45

#define MAX_R 100000

struct BFSNode{
    int digitCapacity;

    int reminderArraySize;
    int reminderArray[MAX1]; // mod 100000 when curVal exceed 100000

    int curVal; // store the val which after processde by reminderArray

    int Reminder;
};
int Num;

typedef struct BFSNode BFSNode;

queue<BFSNode> BFSQueue;

int getDigitCapacity(int num) {
    int res = 0;
    while(num) {
        res++;
        num /= 10;
    }
    return res;
}

char fragment[32][6] = {
    "00000", "00001","00010","00011",
    "00100", "00101","00110","00111",
    "01000", "01001","01010","01011",
    "01100", "01101","01110","01111",
    "10000", "10001","10010","10011",
    "10100", "10101","10110","10111",
    "11000", "11001","11010","11011",
    "11100", "11101","11110","11111"
    };

char BFSFlag[300];

char BFS() {
    while (BFSQueue.size()) {
        BFSQueue.pop();
    }

    BFSNode begiNode;
    begiNode.curVal = 1;
    begiNode.digitCapacity = 1;
    begiNode.reminderArraySize = 0;
    memset(begiNode.reminderArray, 0 ,sizeof(begiNode.reminderArray));
    memset(BFSFlag, 0, sizeof(BFSFlag));
    begiNode.Reminder = 1 % Num;
    BFSFlag[begiNode.Reminder] = 1;
    BFSQueue.push(begiNode);

    while(BFSQueue.size()) {
        BFSNode curNode = BFSQueue.front();
        BFSQueue.pop();
        int curVal = curNode.curVal;
        int curDigitCapacity = curNode.digitCapacity;
        int curReminder = curNode.Reminder;
        // printf("R %d C %d Num %d\n", curReminder, curDigitCapacity, Num);

        int congruentNum = curReminder * 10;
        
        // check 0
        if (congruentNum % Num == 0) { // find it !
            for (int i = 0; i < curNode.reminderArraySize; i++) {
                // printf("%s", fragment[curNode.reminderArray[i]]);
                printf("%05d", curNode.reminderArray[i]);
            }
            int tmpD = getDigitCapacity(curVal*10);
            // printf("\n%d %d\n", tmpD, curDigitCapacity + 1);
            // if (tmpD < curDigitCapacity + 1) {
            //     for (int i = 0; i < curDigitCapacity + 1 - tmpD; i++) {
            //         printf("0");
            //     }
            // }
            printf("%0*d\n", curDigitCapacity + 1, curVal*10);
            return 1;
        } else {
            BFSNode newNode;
            newNode.Reminder = congruentNum % Num;
            if (!BFSFlag[newNode.Reminder]) {
                newNode.digitCapacity = curDigitCapacity + 1;
                BFSFlag[newNode.Reminder] = 1;
                // printf("%d -> %d\n", curReminder, newNode.Reminder);
                memcpy(newNode.reminderArray, curNode.reminderArray, sizeof(newNode.reminderArray));
                newNode.reminderArraySize = curNode.reminderArraySize;
                int newVal = curVal * 10;
                if (newNode.digitCapacity > 5) {
                    newNode.reminderArray[newNode.reminderArraySize] = newVal/10;
                    newNode.reminderArraySize++;
                    newNode.curVal = newVal%10;
                    newNode.digitCapacity = 1;
                } else {
                    newNode.curVal = newVal;
                }
                BFSQueue.push(newNode);
            }
        }

        // check 1
        if ((congruentNum +1) % Num == 0) {// find it !
            // printf("%d\n", congruentNum +1);
            for (int i = 0; i < curNode.reminderArraySize; i++) {
                // printf("%s", fragment[curNode.reminderArray[i]]);
                printf("%05d", curNode.reminderArray[i]);
            }
            int tmpD = getDigitCapacity(curVal*10 + 1);
            // printf("\n%d %d\n", tmpD, curDigitCapacity + 1);
            // if (tmpD < curDigitCapacity + 1) {
            //     for (int i = 0; i < curDigitCapacity + 1 - tmpD; i++) {
            //         printf("0");
            //     }
            // }
            printf("%0*d\n", curDigitCapacity + 1, curVal*10 + 1);
            return 1;
        } else {
            BFSNode newNode;
            newNode.Reminder = (congruentNum + 1) % Num;
            if (!BFSFlag[newNode.Reminder]) {
                BFSFlag[newNode.Reminder] = 1;
                newNode.digitCapacity = curDigitCapacity + 1;
                // printf("%d -> %d\n", curReminder, newNode.Reminder);
                memcpy(newNode.reminderArray, curNode.reminderArray, sizeof(newNode.reminderArray));
                newNode.reminderArraySize = curNode.reminderArraySize;
                int newVal = curVal * 10 + 1;
                if (newNode.digitCapacity > 5) { // if digits has been 6 long
                    newNode.reminderArray[newNode.reminderArraySize] = newVal/10;
                    // printf("put %d %d\n", newNode.reminderArraySize, newNode.reminderArray[newNode.reminderArraySize]);
                    newNode.reminderArraySize++;
                    newNode.curVal = newVal%10;
                    newNode.digitCapacity = 1;
                } else {
                    newNode.curVal = newVal;
                }
                BFSQueue.push(newNode);
            }
        }
    }
    // printf("finished\n");
    return 0;
}

void solve() {
    char res = BFS();
}

char Only1OR0(int num) {
    while(num) {
        int lowest = num%10;
        if (lowest != 0 && lowest != 1) {
            return 0;
        }
        num = num/10;
    }
    return 1;
}

int main() {
    while(1) {
        scanf("%d", &Num);
        if (Num == 0) {
            return 0;
        } else if (Only1OR0(Num)) {
            printf("%d\n", Num);
        } else {
            solve();
        }
    }
}

很棒的一道题,

不看解答还真想不到这道题能用BFS解，其实BFS的思路倒是比较简单：

对于给定的数N

先从1位开始：只能选择 1（0不是合法解）， 检查 1%N == 0，如果不行：

那么增加到两位： 10 ，11，再检查，如果不行：

增加到3位： 100， 101， 110， 111。。。。

就这样依次检查，每次扩展的新的数值 都是原来的两倍，等于每次BFS时，每个节点都有两条边到新的节点。

这就是基本的思路，但是会有很多实现的问题：

每次增加数位递增的数值在题目里最多会到200位，long long都搞不定（不过因为本题数据弱，真这么搞也行），首先想到的就是大数，

但是考虑到效率和内存占用，应该是满足不了本题的需求的，因此这时候，就需要伟大的同余定理出场了：

题目要求检查的其实就是能否被N整除，那么根据同余定理：

(aN + b)%N ==  ((a+x)N + b)%N, 即对于再大的数，在考察同余时（这里的整除表现为余数==0），都可以缩小为一个足够小的数。

在本题中，就这样做：

对某一次的在要检查的数X最后增加一位数（0/1），而增加的基础，也就是上一次的数（X）%N的余数 是 R，

那么有 X ==aN + R， 那么 在X后面增加一位数，其值就变为了 10*X（增加0）/10*X +1 (增加1)，

这时候，就要检查了10*X/10*X+1 能否被N整除了，

10*X = 10*（aN + R） = 10 *aN + R*10,  而 （10 *aN + R*10）%N = R*10%N，R*10是一个足够小的可以直接用int表示的值（根据题意，R<=200）,

这样就克服了增加数位后数值太大的问题了，10*X+1同理， 和 R*10 + 1同N余，

如果在增加了一位以后还不能整除N，那么记下这一次的余数R0/R1（这一次的数X就表示为 a1N + R0/R1）， 在下一次增加数位的时候计算余数，

就这样，一直到找到了能整除N的数X。

BFSNode 里携带的信息要包含此次X%N的值，为检测两个新的BFSNode增加位后的X能否整除N.

除了上面这个问题外，还有另外一个问题：

最后要求输出能整除N的X，而X可能会很长，如果每个BFSNode中直接用字符串类型表示X，可能会MLE，

这时候，也需要一种表示方式能压缩X，可以这么做：

BFSNode中不用字符串数组保存，而是用int数组L，不同的是，L每个数组值保存的是X的5位值（其实5位保守了，完全可以10位，只要不超过int的范围就可以）。

举个例子： X 是 10010 00101 00011 01111， 一共有20位，那么可以分为4段，每一段直接数值保存在L数组中：

L数组内容就是:  L[0] == 10010, L[1] == 00101, L[2] = 00011, L[3] =  01111, 这样就保存了X值，最后输出X的时候，顺序输出L即可，

一些实现细节就是，BFSNode要维护一个当前X的值V和当前的数位D，每次增加数位，D++，X*10/X*10+1， 如果D >5，那么就把X/10的值保存在L中，

而X值刷新为X%10， 注意最后输出的时候，要补0，比如L[1] = 10000, L[2] = 00000(数字是0)， 那么输出时要 printf("%50d")补0. 不然就从 10000 00000 -> 10000 0了，最后剩余的不满5位的X也要注意这个问题。

其实上面这个也是不是最好的办法，最好的办法是直接上位，因为X只有1和0，因此完全可以用一位bit来保存X的某一位，

这样最多需要200位，并且，每次增加新数位的操作也很简单，只需左移一位就可以。

最后是一个优化的问题，

可以注意到，上面的求余数过程中，如果在某一次得到一个余数R， 另外一次也得到一个余数R， 两次的后继操作会一模一样，

这就说明了，在求X时，最多遍历所有的<N的余数，就可以得到X了，因此要加一个余数的FLAG，标示此余数之前是否出现过，如果出现过直接pass不处理（否则是一轮同样的操作），这样就大大减少了运算次数。

检测答案的时候，被python坑了，得到199的X其实对的，不过python因为精度问题，X/199没表示成整数，还是用了divmod才OK.

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6