Нахождение целых степенных корней

Я думаю, что подход грубой силы должен работать: попробуйте все e от 2 (1 - тривиальное решение) и выше, взяв r = n ^ 1/e, double. Если r меньше 2, остановитесь. В противном случае вычислите ceil(r)^e и floor(r)^e и сравните их с n (вам нужны ceil и floor для компенсации ошибок в представлениях с плавающей запятой). Предполагая, что ваши целые числа умещаются в 64 бита, вам не нужно будет пробовать более 64 значений e.

Вот пример на С++:

#include <iostream>
#include <string>
#include <sstream>
#include <math.h>
typedef long long i64;
using namespace std;
int main(int argc, const char* argv[]) {
    if (argc == 0) return 0;
    stringstream ss(argv[1]);
    i64 n;
    ss >> n;
    cout << n << ", " << 1 << endl;
    for (int e = 2 ; ; e++) {
        double r = pow(n, 1.0 / e);
        if (r < 1.9) break;
        i64 c = ceil(r);
        i64 f = floor(r);
        i64 p1 = 1, p2 = 1;
        for (int i = 0 ; i != e ; i++, p1 *= c, p2 *= f);
        if (p1 == n) {
            cout << c << ", " << e << endl;
        } else if (p2 == n) {
            cout << f << ", " << e << endl;
        }
    }
    return 0;
}

При вызове с 65536 он выдает следующий вывод:

65536, 1
256, 2
16, 4
4, 8
2, 16

Сначала найдите простую факторизацию n: n = p1e1 p2e2 p3e3 ...

Затем найдите наибольший общий делитель g чисел e1, e2, e3, ..., используя алгоритм Евклида.

Теперь для любого фактора e из g вы можете использовать:

b = p1e1/e p2e2/e p3e3/e ...

И у вас есть n = be.

Удовлетворит ли мой подход ваши потребности, зависит от размеров задачи.

Во-первых, есть одно очевидное решение: e = 1, верно? С этого момента, если вы хотите найти все решения: все алгоритмы, которые я могу придумать, требуют найти какой-то простой множитель n. Если это всего лишь одна независимая задача, ничего лучше, чем перебор простых чисел, нельзя сделать (если я не ошибаюсь). После того, как вы найдете первый простой множитель p и соответствующий ему показатель степени (то есть наибольшее число k, такое что p^k/n), вам нужно проверить на e только делители k. Для каждого такого показателя степени l (опять же l повторяет все делители k) вы можете использовать бинарный поиск, чтобы увидеть, является ли корень l-го числа n целым числом (эквивалентно поиску нового решения).

Смешайте подходы interjay и dasblinkenlight. Сначала найдите все малые простые множители (если они есть) и их показатели в простой факторизации n. Соответствующее значение "маленький" зависит от n, для среднего размера n может быть достаточно p <= 100, для большого более подходящим может быть n, p <= 10000 или p <= 10^6. Если вы найдете малые простые множители, вы знаете, что e должно делить наибольший общий делитель всех найденных вами показателей степени. Довольно часто gcd будет 1. В любом случае, диапазон возможных показателей будет уменьшен, если n не имеет малых простых делителей, вы знаете, что e <= log(n)/log(small_limit), что является хорошим сокращением от log(n)/log(2), если вы нашли пару маленьких простых множители, gcd их показателей g, а оставшийся сомножитель n равен m, вам нужно только проверить делители g, не превышающие log(m)/log(small_limit).