Find The Multiple [poj 1426]

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

2
6
19
0

Sample Output

10
100100100100100100
111111111111111111

题目大意：输入一个正整数 n(1 <= n <= 200)，找到一个只由 0 和 1 构成的十进制数 m(长度 <= 100)。若有多个解，选取其中一个即可。

思路：BFS（参考自：POJ 1426 – Find The Multiple - 卉卉卉大爷 - 博客园 (cnblogs.com)）

BFS 过程：

• 队列元素的构成：{vector数组，对应余数}
• 每次更新数num，在num后选择添加 0 还是 1，并且计算余数
• vis数组标记已经访问过的余数，剪枝
• 每次更新余数的时候，新的余数的计算公式mod = (mod * 10 + i) % n，对于某些出现过的余数，经过这个公式只会重复出现。
• 新的数对应计算出的余数 = 0 时，代表能够整除，打印输出

AC代码：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int n;

struct Node{
    vector<int> num;
    int mod; // num对应余数
};

void bfs(){
    bool vis[200] = {false}; // 判断重复余数，剪枝
    queue<Node> q;
    Node start;
    start.num.push_back(1), start.mod = 1 % n;
    q.push(start);
    vis[1] = true;

    while(!q.empty()){
        Node st = q.front();
        q.pop();

        if(st.mod == 0){
            for(int i = 0; i < st.num.size(); i ++) cout << st.num[i];
            cout << '\n';
            return;
        }

        for(int i = 0; i <= 1; i ++){
            Node end;
            int x = st.mod; // 余数
            end.num = st.num;
            end.num.push_back(i);
            x = (x * 10 + i) % n; // 计算新余数

            if(!vis[x]){
                end.mod = x;
                q.push(end);
                vis[x] = true; // 标记
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    while(cin >> n && n != 0){
        bfs();
    }

    return 0;
}