С++ Степень! Даю 25 баллов, только на С++!
есть код прошедший 12 тестов из 15(см. текстовый файл)
Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Входные данные
Во входных данных содержится единственное число A (1≤A≤10^9 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…).
Выходные данные
Выведите число N.
Примеры
Ввод
Вывод
1
1
8
4
Answers & Comments
Тесты проваливаются на степенях двойки (A=2^n) при n >= 5
Напишу два решения. Первое просто показывает алгоритм, но имеет ограничение на N (результат не может быть больше 15 из-за переполнения unsigned long long)
Второе по своей сути такое же, но не имеет ограничений. Однако для этого понадобится особый тип данных big_integer. Вторую реализацию прикрепил к ответу в виде текстового файла из-за ограничения на количество символов в ответе.
// первое решение
#include <iostream>
typedef unsigned long long ulong;
ulong pow(int num, int pow);
int main()
{
int a = 0;
std::cin >> a;
int n = 0;
while (n++ <= a)
{
if (pow(n, n) % a == 0)
{
std::cout << n << std::endl;
break;
}
}
return 0;
}
ulong pow(int num, int pow)
{
ulong res = num;
for (int i = 1; i < pow; ++i)
res *= num;
return res;
}