如“数学”参考中所述，结果与模
A下10的幂的同余有关。
如果
n = sum_i a[i] 10^i
那么
n modulo A = sum_i a[i] b[i]
如果a[i]等于0或1，且b[i] = (10^i)模A
那么问题就是找到最小的a[i]序列，使得它们的和模A等于0。
从图的角度来看，我们需要找到到0模A的最短路径。
使用BFS通常很适合找到这样的路径。问题在于可能会指数级增加要访问的节点数量。在这里，通过拒绝已经获得（在程序中看到的向量used）的模A的和的节点，我们可以确保最终得到的节点数量小于A。请注意，为了获得最小的数字，这种拒绝是必需的。
下面是一个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数组），现在只使用一个数组而不是两个
- 使用了一种类似于meet-in-the-middle的过程：首先，函数
mem_gen记忆了所有相关的01序列，最多有N_DIGIT_MEM（=20）个数字。然后主过程multiple2生成有效的01序列“在前20个数字之后”，然后在记忆中寻找“补充序列”，使得两者的连接是一个有效序列
使用这个新程序，当N = 60000007时，在我的电脑上大约需要600毫秒才能提供正确结果（100101000001001010011110111，27位数）。
编辑2
与其限制第一步记忆化的数字数量，我现在使用内存大小作为阈值，因为这个大小不仅取决于数字数量，还取决于输入数字。请注意，这个阈值的最佳值将取决于输入数字。在这里，我选择了50k作为折衷方案的阈值。对于20k的阈值，对于60000007，我在36毫秒内获得了正确结果。此外，对于100k的阈值，最坏情况99999999可以在5秒内解决。
我进行了不到10^9的值的不同测试。在几乎所有测试的情况下，结果都在1秒内提供。然而，我遇到了一个角落案例N = 99999999，其中结果由72个连续的“1”组成。在这种特殊情况下，程序需要大约6.7秒。对于60000007，正确结果在69毫秒内获得。
以下是新程序：
#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_) {};
};
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;
const int threshold_size_mem = 50000;
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;
}
return false;
}
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()) {
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;
}
N的最大值是多少？ - nice_dev