Задача на c++ - Вопросы по С+

Вопрос Задача на c++

Регистрация
20 Дек 2013
Сообщения
102
Репутация
-2
Спасибо
0
Монет
0
Напишите код на C++, пожалуйста. Не надо писать, что уже решали. Те решения не работают.

Степень

Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A. Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.

Входные данные

Во входных данных содержится единственное число A

(1≤A≤109

— на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы «завалить» кого-нибудь…).

Выходные данные

Выведите число N
 
Регистрация
25 Май 2013
Сообщения
93
Репутация
0
Спасибо
0
Монет
0
Подключи библиотеки, открой функцию, напиши, что возвратить надо... И всё, тройка обеспечена.
 
Регистрация
24 Фев 2013
Сообщения
62
Репутация
-1
Спасибо
0
Монет
0
```cpp
#include <iostream>
#include <unordered_map>

std::unordered_map<int, int> factorize(int a) {
std::unordered_map<int, int> factors;
int i = 2;
while (i * i <= a) {
while (a % i == 0) {
factors++;
a /= i;
}
i++;
}
if (a > 1) {
factors[a] = 1;
}
return factors;
}

int legendre(int n, int p) {
int count = 0;
while (n) {
n /= p;
count += n;
}
return count;
}

int minimal_n(int a) {
if (a == 1) {
return 1;
}
std::unordered_map<int, int> factors = factorize(a);
int max_n = 1;
for (const auto& [p, k] : factors) {
int low = 1, high = k * p;
while (low < high) {
int mid = (low + high) / 2;
if (legendre(mid, p) >= k) {
high = mid;
} else {
low = mid + 1;
}
}
max_n = std::max(max_n, low);
}
return max_n;
}

int main() {
int a;
std::cin >> a;
std::cout << minimal_n(a) << std::endl;
return 0;
}
```
 
Регистрация
6 Дек 2013
Сообщения
92
Репутация
1
Спасибо
0
Монет
0
ну короче тебе надо найти такое n чтоб n в степени n делилось на а просто перебирай n от 1 и выше проверяй if pow(n,n) % a == 0 выводи n и всё дело сделано
 
Сверху Снизу