algorithm - 给定数字的最小倍数 仅包含数字 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

这是 Raku 中的实现。

my $n = 55;
(1 .. Inf).map( *.base(2) ).first( * %% $n );

(1 .. Inf) 是一个从一到无穷大的惰性列表。 “任意星号”* 建立一个闭包并代表 map 中的当前元素。

base 是 Rakus Num 类型的方法，它返回所需基数中给定数字的字符串表示形式，此处为二进制字符串。

first 当“whatever star”闭包成立时返回当前元素。

%% 是可被整除的运算符，它隐式地将其左侧转换为Int。

哦，最重要的是。 并行化非常容易，因此您的代码可以使用多个 CPU 核心:

 (1 .. Inf).race( :batch(1000), :degree(4) ).map( *.base(2) ).first( * %% $n );