@mbcsoft

Как найти минимальное число N, которое в степени N делится на A?

FREE PASCAL. A не больше 10000

К примеру A = 8
1^1 = 1
2^2 = 4
3^3 = 27
4^4 = 256 - делится на A. Оно подходит => N = 4

С помощью перебора можно было возвести не более, чем 10^10, далее выкидывалась ошибка. (т.к. переходило за границу real 2.9e-39 .. 1.7e+38, а другие типы были недоступны )

P.S. Доступные типы integer, longint, real, string, array, boolean, byte, word
  • Вопрос задан
  • 2627 просмотров
Решения вопроса 2
fornit1917
@fornit1917
Все дело в математике.

Сначала сделайте факторизацию A. Представьте его в виде П(ai^pi), i=1..k, где ai - различные простые числа.
(т.е. a1^p1 * a2^p2 * ... * ak^pk).
Очевидно, что N надо искать в виде П(ai^qi), i=1..k. Надо найти степени qi. Как это сделать?
N^N = П(ai^(N*qi)). Сопоставляя с формулой для A и понимая, что N^N должно быть не меньше A и делиться на него, получаем следующее ограничение:

N*qi >= pi или qi*(ai^qi) >= pi для всех i.

Нам нужно найти минимальное П(ai^qi) при обозначенном выше ограничении. Дальше, я думаю, справитесь.
Ответ написан
Комментировать
@mbcsoft Автор вопроса
Решение задачи свелось к перебору. Для обхода границ real использовалось деление\умножение столбиком (два массива цифр).
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
AnnTHony
@AnnTHony
Интроверт
Поиск уже предполагает перебор.
Но можно его немного упростить...
Примерно такой алгоритм:
- перебираем все числа в диапазоне 1...А-1, дальше уже смысла нет, ибо наименьшее число будет само же А
Соответственно в вашем примере 10^10 умножать не нужно, т.к. 8<10
Ответ написан
Ваш ответ на вопрос

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

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