Как упомянуто в «математической» справке, результат связан с конгруэнцией степени 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.
BFS, как правило, хорошо приспособлен для поиска такого пути. Проблема заключается в возможном экспоненциальном увеличении количества посещаемых узлов. Здесь мы должны были получить число узлов меньше A, отклоняя узлы, сумма которых (по модулю 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 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;
}
EDIT
В приведенной выше программе используется вид запоминание, чтобы ускорить процесс, но для больших входов память становится слишком большой. Как указано в комментарии, например, он не может обработать случай N = 60000007.
Я немного улучшил скорость и диапазон с помощью следующих модификаций:
- Функция (
reduction) был создан для упрощения поиска, когда входное число делится на 2 или 5 - Для запоминания узлов (массив
nodes) теперь используется только один массив вместо двух - Используется разновидность промежуточной процедуры: на первом шаге функция
mem_gen запоминает все соответствующие 01 последовательности до N_DIGIT_MEM (= 20) цифр. Затем основная процедура multiple2 генерирует действительные последовательности 01 «после 20 первых цифр», а затем в памяти ищет «дополнительную последовательность», так что объединение обоих является действительной последовательностью
С Эта новая программа N = 60000007 обеспечивает хороший результат (100101000001001010011110111, 27 цифр) примерно за 600 мс на моем P C.
РЕДАКТИРОВАТЬ 2
Вместо ограничения количества цифр для запоминания на первом шаге, я теперь использую порог для размера памяти, так как этот размер не зависит только от количества цифр, но и от номера ввода. Обратите внимание, что оптимальное значение этого порога будет зависеть от входного числа. Здесь я выбрал в качестве компромисса порог в 50к. С порогом 20к, для 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_) {};
};
// 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;
}