如“数学”参考中所述，结果与 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
然后问题是找到最小 a[i]序列，使得总和等于 0 模A。
从图 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;
}