Как найти минимальное число 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, а другие типы были недоступны )
Сначала сделайте факторизацию 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) при обозначенном выше ограничении. Дальше, я думаю, справитесь.
Поиск уже предполагает перебор.
Но можно его немного упростить...
Примерно такой алгоритм:
- перебираем все числа в диапазоне 1...А-1, дальше уже смысла нет, ибо наименьшее число будет само же А
Соответственно в вашем примере 10^10 умножать не нужно, т.к. 8<10
mbcsoft: но мне кажется что должен быть алгоритм более практичный, чем простой перебор. Например, можно упростить еще: взять квадратный корень из А и, если есть - отбросить дробную часть и прибавить единицу- это будет нижний предел, от которого надо начинать искать числа. Корень из 257 ~ 8, значит начинать надо с 9 искать.
