Автоморфными называются числа, которые содержатся в последних разрядах их квадрата, например, десятичные числа: 52 = 25, 252 = 625. Автоморфные числа существуют в системе счисления, основание n которой не должно быть простым числом или его степенью (n = 6,10,12,14…). Составьте алгоритм нахождения k автоморфных чисел в заданной системе счисления.
Помогите пожалуйста!!!
програмировать на С++
Ответы
#include <iostream>
#include <string>
using namespace std;
// Функция для преобразования целого числа в строку в заданной системе счисления
string itoa(int num, int base) {
string result = "";
char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
while (num > 0) {
result = digits[num % base] + result;
num /= base;
}
return result;
}
// Функция для проверки, является ли число простым или его степенью
bool isPrimeOrPower(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
int power = i;
while (power < num) {
power *= i;
}
return power == num;
}
}
return true;
}
int main() {
int n, k; // основание системы счисления и количество автоморфных чисел
cout << "Введите основание системы счисления: ";
cin >> n;
cout << "Введите количество автоморфных чисел: ";
cin >> k;
// Проверяем, что n не является простым числом или его степенью
if (isPrimeOrPower(n)) {
cout << "Основание системы счисления должно быть составным числом, не являющимся степенью другого числа.\n";
return 0;
}
int count = 0; // счетчик найденных автоморфных чисел
int num = 1; // текущее число
cout << "Первые " << k << " автоморфных чисел в системе счисления с основанием " << n << ":\n";
while (count < k) {
int square = num * num; // квадрат текущего числа
string num_str = itoa(num, n); // строковое представление текущего числа
string square_str = itoa(square, n); // строковое представление квадрата
// Сравниваем последние символы строк num_str и square_str
bool isAutomorphic = true;
for (int i = 0; i < num_str.length(); i++) {
if (num_str[num_str.length() - i - 1] != square_str[square_str.length() - i - 1]) {
isAutomorphic = false;
break;
}
}
// Если текущее число является автоморфным, выводим его на экран и увеличиваем счетчик
if (isAutomorphic) {
cout << num_str << "\n";
count++;
}
// Увеличиваем текущее число на 1
num++;
}
return 0;
}