任意给定一个正整数N，求一个最小的正整数M(M>1)，使得N*M的十进制表示形式里只含有1和0。...C++BFS代码

以下是基于BFS的C++代码实现：

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

int minMultiple(int n) {
    queue<pair<int, int>> q;
    unordered_set<int> visited;

    q.push({1, 1});

    while (!q.empty()) {
        auto curr = q.front(); q.pop();
        int num = curr.first, steps = curr.second;

        if (num % n == 0) {
            return num;
        }

        if (visited.count(num % n) == 0) {
            visited.insert(num % n);

            q.push({num * 10, steps + 1});
            q.push({num * 10 + 1, steps + 1});
        }
    }

    return -1;
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    int res = minMultiple(n);

    if (res == -1) {
        cout << "Cannot find a multiple of " << n << " with only 1s and 0s." << endl;
    } else {
        cout << "The smallest multiple of " << n << " with only 1s and 0s is: " << res << endl;
    }

    return 0;
}

代码思路：

- 从1开始，每次将当前数字乘以10或者乘以10再加上1，然后模N，如果模N的结果为0，则当前数字就是所求的结果；
- 如果模N的结果没有出现过，则将其加入队列并标记为已访问，继续进行BFS；
- 如果队列为空但是没有找到符合条件的数字，则说明不存在这样的数字。

时间复杂度：$O(\frac{N}{\log N})$ （根据题目所给数据范围，实际运行时间很短）