Sau*_*rma 5 algorithm graph graph-algorithm
给你一个整数 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");
}
}
}
这是 Raku 中的一个实现。
my $n = 55;
(1 .. Inf).map( *.base(2) ).first( * %% $n );
(1 .. Inf)是一个从一到无穷大的懒惰列表。“whatever star”*建立一个闭包并代表map.
base是一种 RakusNum类型的方法，它返回所需基数中给定数字的字符串表示形式，这里是一个二进制字符串。
first 当“whatever star”闭包适用时返回当前元素。
的%%是divisible by运营商，它含蓄地蒙上了左侧Int。
哦，最重要的是。这是很容易对并行这一点，所以你的代码可以使用多个CPU内核：
(1 .. Inf).race( :batch(1000), :degree(4) ).map( *.base(2) ).first( * %% $n );
正如“数学”参考文献中提到的，结果与 10 modulo 次方的同余有关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
那么问题是找到最小 a[i]序列，使得总和等于 0 modulo A。
从图的角度来看，我们必须找到模 A 到零的最短路径。
BFS 通常很适合寻找这样的路径。问题是要访问的节点数量可能呈指数级增长。在这里，通过拒绝已经获得其总和（模 ）的节点，我们肯定会得到小于 的节A点数（参见程序中的向量）。请注意，为了最终获得最小数量，需要进行此拒绝。Aused
这是一个 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 ten = 10 % A;
int pow_ten = 1;
if (A == 0) return "0";
if (A == 1) return "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;
}
编辑
上面的程序使用一种记忆来加速过程，但对于大输入，内存变得太大。例如，如注释中所示，它无法处理 N = 60000007 的情况。
我通过以下修改稍微提高了速度和范围：
reduction) 是为了简化输入数字可被 2 或 5 整除时的搜索nodes数组），现在只使用一个数组而不是两个mem_gen存储所有相关的 01 序列，最多 N_DIGIT_MEM (=20) 位。然后主程序multiple2在“前 20 个数字之后”生成有效的 01 序列，然后在内存中查找“互补序列”，以便两者的串联是一个有效序列使用这个新程序，案例 N = 60000007 在我的 PC 上大约 600 毫秒内提供了良好的结果（100101000001001010011110111，27 位数字）。
编辑2
我现在没有在第一步中限制记忆的位数，而是使用内存大小的阈值，因为该大小不仅取决于位数，还取决于输入的数字。请注意，该阈值的最佳值取决于输入数量。在这里，我选择了 50k 的阈值作为折衷方案。阈值为 20k，对于 60000007，我在 36 毫秒内获得了良好的结果。此外，以100k为阈值，最坏情况99999999在5s内就可以解决。
我做了不同的测试，其值小于 10^9。在几乎所有测试案例中，结果都会在不到 1 秒的时间内提供。然而，我遇到了一个极端情况 N=99999999，其结果由 72 个连续的“1”组成。在本例中，程序大约需要 6.7 秒。对于60000007，在69ms内获得了良好的结果。
这是新程序：
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <cmath>
#include <algorithm>
std::string reverse (std::string s) {
std::string res {s.rbegin(), s.rend()};
return res;
}
struct node {
int sum = 0;
std::string s;
node (int sum_ = 0, std::string s_ = ""): sum(sum_), s(s_) {};
};
// This function simplifies the search when the input number is divisible by 2 or 5
node reduction (int &X, long long &pow_ten) {
node init {0, ""};
while (1) {
int digit = X % 10;
if (digit == 1 || digit == 3 || digit == 7 || digit == 9) break;
switch (digit) {
case(0):
X /= 10;
break;
case(2):
case(4):
case(6):
case(8):
X = (5*X)/10;
break;
case(5):
X = (2*X)/10;
break;
}
init.s.push_back('0');
pow_ten = (pow_ten * 10) % X;
}
return init;
}
const int N_DIGIT_MEM = 30; // 20
const int threshold_size_mem = 50000;
// This function memorizes all relevant 01 sequences up to N_DIGIT_MEM digits
bool gene_mem (int X, long long &pow_ten, int index_max, std::map<int, std::string> &mem, node &result) {
std::vector<node> nodes;
std::vector<bool> used (X, false);
bool start = true;
for (int index = 0; index < index_max; ++index){
if (start) {
node x = {int(pow_ten), "1"};
nodes.push_back (x);
} else {
for (node &x: nodes) {
x.s.push_back('0');
}
int n = nodes.size();
for (int i = 0; i < n; ++i) {
node y = nodes[i];
y.sum = (y.sum + pow_ten) % X;
y.s.back() = '1';
if (used[y.sum]) continue;
used[y.sum] = true;
if (y.sum == 0) {
result = y;
return true;
}
nodes.push_back(y);
}
}
pow_ten = (10 * pow_ten) % X;
start = false;
int n_mem = nodes.size();
if (n_mem > threshold_size_mem) {
break;
}
}
for (auto &x: nodes) {
mem[x.sum] = x.s;
}
//std::cout << "size mem = " << mem.size() << "\n";
return false;
}
// This function generates valid 01 sequences "after the 20 first digits" and then in the memory
// looks for a "complementary sequence" such that the concatenation of both is a valid sequence
std::string multiple2 (int A) {
std::vector<node> nodes;
std::map<int, std::string> mem;
int ten = 10 % A;
long long pow_ten = 1;
int digit;
if (A == 0) return "0";
int X = A;
node init = reduction (X, pow_ten);
if (X != A) ten = ten % X;
if (X == 1) {
init.s.push_back('1');
return reverse(init.s);
}
std::vector<bool> used (X, false);
node result;
int index_max = N_DIGIT_MEM;
if (gene_mem (X, pow_ten, index_max, mem, result)) {
return reverse(init.s + result.s);
}
node init2 {0, ""};
nodes.push_back(init2);
while (1) {
for (node &x: nodes) {
x.s.push_back('0');
}
int n = nodes.size();
for (int i = 0; i < n; ++i) {
node y = nodes[i];
y.sum = (y.sum + pow_ten) % X;
if (used[y.sum]) continue;
used[y.sum] = true;
y.s.back() = '1';
if (y.sum != 0) {
int target = X - y.sum;
auto search = mem.find(target);
if (search != mem.end()) {
//std::cout << "mem size 2nd step = " << nodes.size() << "\n";
return reverse(init.s + search->second + y.s);
}
}
nodes.push_back(y);
}
pow_ten = (pow_ten * ten) % X;
}
}
int main() {
std::cout << "input number: ";
int n;
std::cin >> n;
std::string res;
auto t1 = std::chrono::high_resolution_clock::now();
res = multiple2(n),
std::cout << "Result = " << res << " ndigit = " << res.size() << std::endl;
auto t2 = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
std::cout << "time = " << duration2/1000 << " ms" << std::endl;
return 0;
}