Question

C++. Степень. Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A. Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу. Входные данные Во входных данных содержится единственное число A (1≤A≤109 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…). Выходные данные Выведите число N.

Answer 1

#include <iostream>

#include <math.h>

int f(int a)

{

for (int n = 1; n <= a; n++)

{

double b = (double)a / n;

if ((int)b == b)

{

b = pow(n, n) / a;

if ((int)b == b)

return n;

}

}

return a;

}

int main(int argc, char *argv[])

{

int a;

std::cin >> a;

std::cout << f(a);

}

Answer 2

Для решения этой задачи, вы можете использовать бинарный поиск, чтобы найти минимальное натуральное N, удовлетворяющее условию. Вот C++ программный код, который решает данную задачу:

cppCopy code
#include <iostream>
using namespace std;

// Функция, которая проверяет, делится ли N в степени N на A
bool isDivisible(long long N, long long A) {
    long long result = 1;
    for (int i = 0; i < N; i++) {
        result *= N;
        if (result > A) {
            return false;
        }
    }
    return result == A;
}

// Функция для нахождения минимального N
long long findMinN(long long A) {
    long long left = 1, right = A;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (isDivisible(mid, A)) {
            return mid;
        }
        if (mid * mid < A) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Если N не найдено
}

int main() {
    long long A;
    cin >> A;

    long long minN = findMinN(A);
    cout << minN << endl;

    return 0;
}

Этот код сначала проверяет, делится ли N в степени N на A, начиная с N = 1 и увеличивая N до тех пор, пока не найдет подходящее значение N. Мы используем бинарный поиск для оптимизации этого процесса.

Запустите эту программу, введите значение A, и она выведет минимальное значение N, которое соответствует условиям задачи.