Во входном файле INPUT.TXT содержится единственное число A (1 ≤ A ≤ 10^9).
В выходной файл OUTPUT.TXT необходимо вывести единственное натуральное число Nтакое, что N в степени N (N, умноженное на себя N раз) делится на A.
Код:
#include <fstream>
using namespace std;
int nod(int a, int b) // Алгоритм Евклида
{
while (a != 0 && b != 0)
if (a > b) a %= b;
else b %= a;
return a + b;
}
int main()
{
int a;
ifstream fin;
fin.open("INPUT.TXT");
fin >> a; // считываем a
fin.close();
ofstream fout;
fout.open("OUTPUT.TXT");
// ПРОВЕРЯЕМ МАЛЕНЬКИЕ ЧИСЛА:
for (int n = 1; n <= 30; n++) // перебираем n
{
int t = a; // временная переменная для a
for (int i = 0; i < n; i++) // n раз мы делим a на нод n и t
{
t /= nod(n, t);
}
if (t == 1) // если после этого t осталась 1
{
fout << n; // то выводим n
return 0; // и выходим
}
}
// ТЕПЕРЬ ПРОВЕРЯЕМ ДЕЛИТЕЛИ:
int n = 1; // n изначально 1
for (int p = 2; p*p <= a; p++)
{
if (a % p == 0) // если p - делитель a
{
n *= p; // тогда n домножаем на p
while (a % p == 0) // и выкидываем из a все p
{
a /= p;
}
}
}
if (a > 1) // если a больше 1, то a - простое число
{
n *= a; // и n умножаем на a
}
fout << n; // печатаем ответ
fout.close();
return 0;
}
Wrong answer на 13 тесте acmp. Что мне исправить?
Попробуйте это решение. Надо начинать с разложения на простые сомножители...
#include <iostream>
#include <map>
using namespace std;
map<unsigned int, unsigned int> factor(unsigned int A)
{
map<unsigned int,unsigned int> m;
while(A%2 == 0) { m[2]++; A /= 2; };
for(unsigned int i = 3; i*i <= A; i += 2)
{
while(A%i == 0) { m[i]++; A /= i; };
}
if (A != 1) m[A]++;
return m;
}
int main(int argc, const char * argv[])
{
unsigned int A;
cin >> A;
if (A == 1) { cout << "1\n"; return 0; }
auto m = factor(A);
unsigned int p = 1;
unsigned int e = 0;
for(const auto& v: m)
{
p *= v.first;
if (v.second > e) e = v.second;
//cout << v.first << " ** " << v.second << endl;
}
if (p < e)
{
unsigned int N = ((e+p-1)/p)*p;
unsigned int M = p, k = 1;
while(M*k < e)
{
for(const auto& v: m)
{
if (v.second == e)
{
M *= v.first;
k++;
}
}
}
cout << ((M < N) ? M : N) << endl;
}
else cout << p << endl;
}
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Как вы думаете, какой вид отношения между классами std::reference_wrapper и std::mutex?ref используется в виде обертки для обертки mutex'а, чтобы представить...