Возведение в степень. Найти ошибку

130
15 января 2020, 12:40

Во входном файле 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. Что мне исправить?

Answer 1

Попробуйте это решение. Надо начинать с разложения на простые сомножители...

#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;
}
READ ALSO
Вид отношения между классами

Вид отношения между классами

Как вы думаете, какой вид отношения между классами std::reference_wrapper и std::mutex?ref используется в виде обертки для обертки mutex'а, чтобы представить...

139
Размер классов при наследовании в С++

Размер классов при наследовании в С++

Если создать 2 таких класса:

145
libssh2 и Channel open failure (connect failed)

libssh2 и Channel open failure (connect failed)

При попытке создать канал как

133