给定数字的最小倍数，只有数字0和1

Question

您得到一个整数N。您必须找到N的最小倍数，它仅由数字0和1组成。由于此倍数可能很大，因此请以字符串形式返回。

返回的字符串不应包含前导零。

例如，

对于N = 55，110是由数字0和1组成的最小整数倍。对于N = 2，答案是10。

我看到了几个相关的问题，但是我的代码找不到问题。这是我的代码，即使在使用map而不是set的情况下，在某些情况下也提供TLE。

#define ll long long
int getMod(string s, int A)
{
    int res=0;
    for(int i=0;i<s.length();i++)
    {
        res=res*10+(s[i]-'0');
        res%=A;
    }
    return res;
}
string Solution::multiple(int A) {
    if(A<=1)
    return to_string(A);

    queue<string>q;
    q.push("1");
    set<int>st;
    string s="1";

    while(!q.empty())
    {
        s=q.front();
        q.pop();
        int mod=getMod(s,A);
        if(mod==0)
        {
            return s;
        }
        else if(st.find(mod)==st.end())
        {
            st.insert(mod);
            q.push(s+"0");
            q.push(s+"1");
        }
    }

}

Answer 1

如“数学”参考文献中所述，结果与10模A的幂的全等有关。

如果

n = sum_i a[i] 10^i

然后

n modulo A = sum_i a[i] b[i]

a[i]等于0或1，并且b[i] = (10^i) modulo A时>]

然后问题是要找到minimum

b[i]系列，以使总和等于0模A。

从图形的角度来看，我们必须找到零模A的最短路径。

BFS通常非常适合找到这样的路径。要访问的节点数量是否可能呈指数增长的问题。在这里，通过拒绝已经获得总和的节点，确保得到少于A的节点数（请参见程序中的向量used）。

这里是C ++程序。该解决方案非常简单，即使不熟悉C ++的人也应该易于理解。

#include <iostream>
#include <string>
#include <vector>

struct node {
    int sum = 0;
    std::string s;
};

std::string multiple (int A) {
    std::vector<std::vector<node>> nodes (2);
    std::vector<bool> used (A, false);
    int range = 0;
    int sum = 0;
    int ten = 10 % A;
    int pow_ten = 1;

    nodes[range].push_back (node{0, "0"});
    nodes[range].push_back (node{1, "1"});
    used[1] = true;

    while (1) {
        int range_new = (range + 1) % 2;
        nodes[range_new].resize(0);
        pow_ten = (pow_ten * ten) % A;

        for (node &x: nodes[range]) {
            node y = x;
            y.s = "0" + y.s;
            nodes[range_new].push_back(y);
            y = x;
            y.sum = (y.sum + pow_ten) % A;
            if (used[y.sum]) continue;
            used[y.sum] = true;
            y.s = "1" + y.s;
            if (y.sum == 0) return y.s;
            nodes[range_new].push_back(y);
        }
        range = range_new;
    }
}

int main() {
    std::cout << "input number: ";
    int n;
    std::cin >> n;
    std::cout << "Result = " << multiple(n) << "\n";
    return 0;
}