Dado un entero x, ¿cómo escribo el código para verificar si x puede escribirse como una potencia n ^ m (x, myn son positivas)?

Es importante saber cuál es el rango para el valor x . Por ejemplo, si es un valor entero de 64 bits, entonces podemos obtener el rango de valores para n y m . En este caso, m puede ser como máximo alrededor de 64.

Ahora tiene 2 posibilidades para abordar el problema.
Intenta enumerar todos los valores para n y encuentra si hay un valor correspondiente m tal que la condición se cumple o prueba todas las posibilidades para my encuentra el valor de n correspondiente. El segundo enfoque es mucho mejor porque solo tiene 64 posibilidades para m y si encuentra n con la búsqueda binaria, nuevamente es como máximo 64 pasos.

Puede usar la búsqueda binaria porque la función exponencial es una función estrictamente creciente si la base es mayor que 1.

El código correspondiente debería funcionar en menos de 50 ms, pero eso depende del idioma que esté utilizando.

Pocas trampas: cuidado con los desbordamientos. Verifique el caso x = 1 por separado.

Necesita obtener una solución a esta ecuación:

x = n ^ m
que se puede escribir como
log (x) = m * log (n)
conoce el valor de log (x), también puede considerar 1 y considerar que la base del registro es x, por lo que ahora tenemos:

1 = m * log (n) a base x

que podemos resolver fácilmente en O (n) u O (m) o el mínimo de ellos como:

float log_n_base_x (número flotante, base flotante)
{
return log10 (número) / log10 (base);
}
int main ()
{
flotador x;
cout << "Ingrese el valor de x:";
cin >> x;
para (int n = 2; n <= 100; n ++)
{
flotante m_float = 1 / log_n_base_x (n, x);
cout << setprecision (3) << x << "=" << setprecision (3) << n << "power" <<
setprecision (3) << m_float << endl;
}
devuelve 0;
}

Ejecución simple:

Notas:

• log (n) base x = (log (n) base 10) / (log (x) base 10).
• Debe especificar el rango de n, es decir, aquí estoy haciendo un bucle de 2 a 100, necesita establecer su propio rango.

Aquí hay una exponenciación al cuadrar el fragmento de Python, que puede resolver su problema

def resolver (x, n, m, MOD):
res = 1
temp = n
mientras que (m! = 0):
si y & 1 == 1:
res = (res * temp)% MOD
temp = (temp * temp)% MOD
m = m >> 1
si res == x:
volver verdadero
falso retorno