Братские числа и Большой Брат натурального числа

Каждое натуральное число имеет бесконечно много кратных ему чисел, в записи которых используются только цифры 0 и 1. Назовём минимальное кратное, обладающее этим свойством, Большим Братом данного числа, а первый и второй сомножители, произведение которых даёт Большого Брата - братскими числами, например, 2 и 5 - братья, а 10 - их Большой Брат, так как 2 * 5 = 10 и 5 * 2 = 10. Это не означает, что у братьев-близнецов 2 и 5 не может быть других братьев, скажем, пятёрка является и братом числа 2022, а 10110 - его Большой Брат (2022 * 5 = 10110, забавно короткий результат получился для числа грядущего года, в отличие от нынешнего). Числа, запись которых уже состоит только из единиц и нулей, ясное дело, имеют братом единицу и сами себе Большие Братья.

Общая картина Братства - это, думаю, отдельный вопрос, который вполне мог бы стать темой для небольшого исследования (все закономерности легко выводятся из факта десятичности и позиционности нашей системы счисления), мне же эта задача хорошо подошла для примера: хотелось побаловаться с числами __int128, но в Studio для 64-битной архитектуры их нормальной поддержки нет, так что в таких случаях проще использовать Qt с компилятором MinGW для x64, там работает.

Соответственно, консольная программа Qt 5.X, представленная ниже, решает нашу задачу.

//Qt 5.X only!
#include <iostream>
#include <vector>

//Служебные функции для __int128
__int128 imax (__int128 a, __int128 b) {
 return (a) > (b) ? (a) : (b);
}

__int128 ipow (__int128 b, __int128 n) {
 if (n == 0) return 1;
 if (n == 1) return b;
 __int128 res = b;
 while (n > 1) {
  res *= b;
  n--;
 }
 return res;
}

__int128 imod (__int128 m, __int128 n) {
 __int128 result = m % n;
 if (result < 0) result += n;
 return result;
}

bool valid (__int128 n) {
 if (n < 0) return false;
 while (n > 0) {
  int r = n % 10;
  if (r > 1) return false;
  n /= 10;
 }
 return true;
}

std::ostream& operator << (std::ostream& os, __int128 n) {
 char buffer[128];
 int pos = (sizeof(buffer) / sizeof(char)) - 1;
 bool negative = false;
 if (n < 0) {
  negative = true;
  n = -n;
 }
 buffer[pos] = 0;
 while (n > 0) {
  int rem = n % 10;
  buffer[--pos] = rem + '0';
  n /= 10;
 }
 if (negative) {
  buffer[--pos] = '-';
 }
 return os << &buffer[pos];
}

//Основной метод
__int128 solve (const __int128 n) {
 if (n == 1) return 1;
 std::vector<__int128> V(n * n, 0);
 V[0] = 1;
 V[1] = 1;
 __int128 m, k, r, j;
 m = 0;
 while (true) {
  m++;
  if (V[(m - 1) * n + imod(-ipow(10, m), n)] == 1) break;
  V[m * n + 0] = 1;
  for (k = 1; k < n; k++) {
   V[m * n + k] = imax(V[(m - 1) * n + k],
                       V[(m - 1) * n + imod(k - ipow(10, m), n)]);
  }
 }
 r = ipow(10, m);
 k = imod(-r, n);
 for (j = m - 1; j >= 1; j--) {
  if (V[(j - 1) * n + k] == 0) {
   r = r + ipow(10, j);
   k = imod(k - ipow(10, j), n);
  }
 }
 if (k == 1) r++;
 return r / n;
}

//Запуск основного метода и контроль вывода
void run (__int128 n) {
 __int128 mult = solve(n);
 if (mult > 0) {
  std::cout << n << " * " << mult << " = " << (n * mult) << '\n';
 }
 else {
  std::cout << n << "(no solution)\n";
 }
}

int main() {
 run(2);
 run(5);
 run(999); //87 бит потребуется
 run(1000);
 run(2021);
 run(2022);
 run(10000);
 //run(100000); //не хватит памяти :(
 return 0;
}

Вывод программы:

2 * 5 = 10
5 * 2 = 10
999 * 111222333444555666777889 = 111111111111111111111111111
1000 * 1 = 1000
2021 * 49481 = 100001101
2022 * 5 = 10110
10000 * 1 = 10000

Самого Большого Брата (для значения 999) проверил умножением вот здесь, совпало.

23.12.2021, 06:54 [635 просмотров]