@dmitrii2004

Найти минимальную степень числа N?

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

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

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

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

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

Выведите число N.

Примеры
Ввод
1
Вывод
1
Ввод
8
Вывод
4
#include <iostream>
using namespace std;
int main()
{
    int a ;
    int n;
    cin >> a;
    for ( int n = 1; n <= 30; n++)
    {
        int t = a;
       int f = t;
         int n1 = n;
        for (int i = 0; i < n; i++)
        {
            while (n1 != 0 and t != 0)
            {
                if (n1 > t)
                {
                    n1 = n % t;
                }
                else
                {
                    t = t % n1;
                }
                
            }
            f = f / (n1 + t);
        }
        if (f == 1)
        {
            cout << n;
            return 0;
        }
    }
      n = 1;
    for (int p = 2; p * p <= a; p++)
    {
        if (a % p == 0)
        {
            n += p;
            while (a % p == 0)
            {
                a /= p;
            }
        }
  }

    if (a > 1)
    {
        n *= a;
}
    cout << n;
    return 0;
}
Помогите пожалуйста сайт пишет, что программа выдаёт неверный ответ
  • Вопрос задан
  • 131 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Решение у задачи такое должно быть:

Поскольку n^n делится на a, то n делится на все простые делители a. Поэтому надо разложить a на множители (пусть a= p1^k1*p2^k2 ...)

Тогда n надо искать в виде k*p1*p2*...

Это самое k надо перебрать от 1 до максимального ki и проверить, что n^n делится на a. Для этого надо подсчитать, сколько раз k делится на p_i (пусть - это q_i). Тогда надо проверить что, (q_i+1)*n >= k_i для всех простых делителей p_i.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
zagayevskiy
@zagayevskiy
Android developer at Yandex
Чёт ппц ты усложнил.

Примерно так будет
n = 1
y = 0
Цикл по всем простым множителям:
xi - текущий простой множитель
yi - количество раз, которое xi встречается
n = n*xi
y = max(y, yi)
Конец цикла

Если n < y то n = n * ceil(y/n)
Ответ n.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы