Задача на автоморфные числа. Язык Си
Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 52 = 25, 252 = 625. Автоморфные числа существуют в системе счисления, основание n которой не должно быть простым числом или его степенью (n = 6,10,12,14…). Составьте алгоритм нахождения k автоморфных чисел в заданной системе счисления.
Нельзя использовать cin,cout,bool.
Есть вот такой код(помогите его изменить так чтобы он выводил не только k чисел, но и в системе счисления заданной пользователем. И нужно убрать bool,cin,cout):
using namespace std;
int cnt_digit(int x); // функция подсчета количества цифр числа
bool isauthomorf(int x);//функция вычисления автоморфного числа
int main() {
unsigned long long cnt;
unsigned long long i = 1;
setlocale(LC_ALL, "rus");
printf("Введите количество необходимых чисел:");
cin >> cnt;//количество нужных чисел
while (cnt) {
if (isauthomorf(i)) {
cout << i << endl; //передвижение на новую строку
--cnt;
}
++i;
}
return 0;
}
bool isauthomorf(int x) {
unsigned long long i = x;
unsigned long long tmp = i;
unsigned long long cnt = cnt_digit(i);
unsigned long long del = 1;
unsigned long long k = 1;
unsigned long long b = 0;
unsigned long long s = 0;
for (int j = 0; j < cnt; ++j)//проверка остатка от деления
del *= 10;
unsigned long long copy_del = del;
while (tmp) { //проверка числа на автоморфность
b = i * (tmp % 10);
tmp /= 10;
b = (b % del) * k;
del /= 10;
k *= 10;
s += b;
}
return ((s % copy_del) == i) ? true : false; //тернарная операция
}
int cnt_digit(int x) {
unsigned long long cnt = 0;
unsigned long long tmp = x;
while (tmp) {
tmp /= 10;
++cnt;
}
return cnt;
}
Ответы (2 шт):
Вот поиск всех автоморфных (без тривиальных 0 и 1) для любых систем счисления. Использовал Boost, искал очередную цифру полуподбором.
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <boost/multiprecision/cpp_int.hpp>
using large = boost::multiprecision::cpp_int;
using namespace std;
string to_sys(large n, large s)
{
char dig[] = "0123456789abcdefghijklmnopqrstuvwxyz";
string r;
while(n)
{
r = dig[int(n%s)] + r;
n /= s;
}
return r;
}
int main(int argc, char * argv[])
{
const large SYS = atoi(argv[1]);
vector<large> q;
for(int i = 2; i < SYS; ++i)
if (i*i%SYS == i)
{
q.push_back(i);
cout << "Found " << i << endl;
}
unsigned long long n = 0;
cout << "N = 0:\n";
for(auto x: q)
{
printf(" x = %20s\n",to_sys(x,SYS).c_str());
printf(" x^2 = %20s\n",to_sys(x*x,SYS).c_str());
}
large tenn = SYS;
for(n = 1; n <= 9; ++n, tenn *= SYS)
{
cout << "N = " << n << ":\n";
for(auto& x: q)
{
large b, p = (x*x/tenn)%SYS;
for(b = 0; b < SYS; ++b)
if (b*(2*x-1)%SYS == (SYS - p)%SYS) break;
x += b*tenn;
printf(" x = %20s\n",to_sys(x,SYS).c_str());
printf(" x^2 = %20s\n",to_sys(x*x,SYS).c_str());
}
}
}
Итерации
Пусть число D записано в виде dkdk-1...d2d1d0, где di - цифра в системе счисления с основанием b. Тогда число равно D = dkbk + dk-1bk-1 + ... + d2b2 + d1b1 + d0b0.
Для возведения в квадрат используем умножение в столбик. Положим c-1 = 0. Начиная с k = 0 вычислим:
sk = ck-1 + (dkd0 + dk-1d1 + dk-2d2 + ... + d2dk-2 + d1dk-1 + d0dk).
ek = sk % b, ck = sk // b. % - остаток от деления, // - деление нацело.
ei - i-тая цифра числа D2.
Пример: D = 10937610
s0 = 0 + 6·6 = 36, e0 = 6, c0 = 3;
s1 = 3 + 7·6 + 6·7 = 87, e1 = 7, c1 = 8;
s2 = 8 + 3·6 + 7·7 + 6·3 = 93, e2 = 3, c2 = 9;
s3 = 9 + 9·6 + 3·7 + 7·3 + 6·9 = 159, e3 = 9, c3 = 15;
s4 = 15 + 0·6 + 9·7 + 3·3 + 7·9 + 6·0 = 150, e4 = 0, c4 = 15;
s5 = 15 + 1·6 + 0·7 + 9·3 + 3·9 + 7·0 + 6·1 = 81, e5 = 1, c5 = 8;...
Продолжать пока есть цифры в D и сk > 0. Недостающие цифры заменить нулями.
Получим D2 = 1196310937610. Выделены цифры, которые были вычислены выше и которые совпадают с цифрами D. Совпадение не случайно - для примера выбрано автоморфное число.
Можно ли дополнить D ещё одним разрядом чтобы получилось семиразрядное автоморфное число? Попробуем. Теперь D = x10937610. Первые шесть разрядов D2 совпадают с предыдущим примером. Следующий разряд:
s6 = 8 + x·6 + 1·7 + 0·3 + 9·9 + 3·0 + 7·1 + 6·x = 103 + 2·6·x, e6 = (103 + 2·6·x) % 10, c6 = (103 + 2·6·x) // 10;
D автоморфное, поэтому e6 = x. Получается сравнение вида (103 + 2·6·x) ≡ x mod 10. Перепишем в виде (2·6 - 1)x ≡ -103 mod 10. Сравнение решается перебором всех цифр. Есть одно решение: x = 7.
D = 7109376, D2 = 50543227109376.
В общем случае нужно будет решать сравнение (2d0 - 1)x ≡ a mod b, где d0 - младшая цифра автоморфного числа, а a - константа определяемая предыдущими цифрами D.
Младшие цифры
Сравнение для младшей цифры автоморфного числа: d02 ≡ d0 mod b. Решается перебором всех цифр. Среди ответов всегда будут 0 и 1 и, может быть, другие цифры.
Перепишем сравнение в виде d0(d0 - 1) ≡ 0 mod b.
Это значит что d0(d0 - 1) делится на b.
Предположим что НОД(2d0 - 1, b) > 1. Тогда существует простое p на которое делятся и 2d0 - 1 и b. Так как b делится на p, а d0(d0 - 1) делится на b, то d0(d0 - 1) делится на p. p простое, следовательно или d0 делится на p или d0 - 1.
Если d0 делится на p, то и (2d0 - 1) - (2d0) делится на p. Тогда -1 делится на p. Противоречие.
Если d0 - 1 делится на p, то и (2d0 - 1) - (2(d0 - 1)) делится на p. Тогда 1 делится на p. Противоречие.
В обоих случаях противоречия. Следовательно НОД(2d0 - 1, b) = 1.
Вспомним сравнение, которое мы решаем для поиска следующей цифры: (2d0 - 1)x ≡ a mod b. Множитель при x взаимно прост с b. Тогда сравнение для любых значений a имеет ровно одно решение.
В итоге имеем алгоритм, который по начальной цифре строит одну единственную бесконечную последовательность старших цифр, любой префикс которых годится в качестве автоморфного числа. Других автоморфных чисел нет.
Реализация
Программа читает базу системы счисления, отыскивает стартовые цифры кроме нуля и единицы. Для каждой стартовой цифры строит цепочку, по мере роста цепочки печатает её префиксы. Если префикс начинается с нуля, он пропускается. Числа перед печатью упорядочиваются.
Программа сама не останавливается. При вызове надо отобрать сколько нужно чисел, и остановить её. Внизу есть пример.
Автоморфные числа 0 и 1 не печатаются:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct number_t {
unsigned long long carry;
int k;
unsigned *digits;
} number_t;
void number_t_resize(number_t *n, int capacity) {
unsigned *digits = realloc(n->digits, capacity * sizeof(n->digits[0]));
if (digits == NULL) {
exit(1);
}
n->digits = digits;
}
int compare_numbers(const void *p1, const void *p2) {
const number_t *n1 = p1;
const number_t *n2 = p2;
assert(n1->k == n2->k);
for (int i = n1->k - 1; i >= 0; --i) {
if (n1->digits[i] < n2->digits[i]) {
return -1;
}
if (n1->digits[i] > n2->digits[i]) {
return 1;
}
}
return 0;
}
int digit_width(int base) {
int w = 0;
for (int i = base - 1; i != 0; i /= 10) {
++w;
}
return w;
}
void print_number(unsigned base, const number_t *n) {
const int w = digit_width(base) + 1;
for (int i = n->k - 1; i >= 0; --i) {
if (base <= 36) {
putchar("0123456789abcdefghijklmnopqrstuvwxyz"[n->digits[i]]);
} else {
printf("%*u", w, n->digits[i]);
}
}
putchar('\n');
}
int main() {
unsigned base;
if (scanf("%u", &base) != 1) {
return 1;
}
int n_numbers = 0;
for (unsigned d = 2; d < base; ++d) {
if (d * d % base == d) {
++n_numbers;
}
}
if (n_numbers == 0) {
return 0;
}
number_t *numbers = malloc(n_numbers * sizeof(numbers[0]));
if (numbers == NULL) {
exit(1);
}
int number_capacity = 1;
{
int i = 0;
for (unsigned d = 2; d < base; ++d) {
const unsigned sum = d * d;
if (sum % base == d) {
assert(i < n_numbers);
number_t *n = &numbers[i];
n->digits = NULL;
number_t_resize(n, number_capacity);
n->carry = sum / base;
n->k = 1;
n->digits[0] = d;
++i;
}
}
assert(i == n_numbers);
}
for (int k = 1; ; ++k) {
qsort(numbers, n_numbers, sizeof(numbers[0]), compare_numbers);
for (int i = 0; i < n_numbers; ++i) {
const number_t *n = &numbers[i];
assert(n->k == k && k <= number_capacity);
if (n->digits[n->k - 1] > 0) {
print_number(base, n);
}
}
if (k == number_capacity) {
number_capacity *= 2;
for (int i = 0; i < n_numbers; ++i) {
number_t_resize(&numbers[i], number_capacity);
}
}
for (int i = 0; i < n_numbers; ++i) {
number_t *n = &numbers[i];
unsigned long long sum = n->carry;
for (int i = 1; i < n->k; ++i) {
sum += n->digits[i] * n->digits[n->k - i];
}
for (unsigned d = 0; d < base; ++d) {
if (sum % base == d) {
assert(n->k == k);
n->carry = sum / base;
n->digits[n->k] = d;
++n->k;
}
sum += 2 * n->digits[0];
}
}
}
}
$ gcc -std=c17 -pedantic -Wall -Wextra -Werror -O3 automorphic-numbers.c $ echo 10 | ./a.out | head -20 5 6 25 76 376 625 9376 90625 109376 890625 2890625 7109376 12890625 87109376 212890625 787109376 1787109376 8212890625 18212890625 81787109376 $ echo 30 | ./a.out | head -20 6 a f g l p 3a 7f ap j6 mg ql 13a 2j6 3mg q7f rap sql 1q7f b2j6 $ echo 210 | ./a.out | head -20 15 21 36 70 85 91 105 106 120 126 141 175 190 196 5 175 28 196 46 141 52 105 75 126 81 91