Par de enteros que tienen diferencia de su quinta potencia como X

Dado un entero X , la tarea es encontrar un par A y B tal que su diferencia de quinta potencia sea X, es decir, A ⁵ – B ⁵ = X . Si no existe tal par, escriba «No es posible».
 

Entrada: X = 33 
Salida: 1 -2 
Explicación:  

Entrada: N = 211 
Salida: -2 -3 
Explicación: 

 

Enfoque ingenuo: una solución simple es usar dos bucles for, uno para A y otro para B, que van desde -10 ⁹ a 10 ⁹ . 
Enfoque eficiente: la idea es reducir el rango de A y B utilizando técnicas matemáticas. 
 

Dado que A ⁵ – B ⁵ = X => A ⁵ ​​= X + B ⁵ . Para que A sea lo más alto posible, B también tiene que ser lo más alto posible, como se desprende de la desigualdad. 
 

Considere A = N y B = N – 1 
=> N ⁵ – (N – 1) ⁵ = X. 
 

 Por expansión binomial sabemos

(p + 1)y ^p <= (y + 1) ^p+1 – y ^p+1 <= (p+1)(y+1) ^p 
 

Entonces podemos decir que el valor máximo de LHS es 4N ⁴ .

Por lo tanto 4N ⁵ <= X 
=> N <= (X/5) ^1/5 . 
=> Esto nos da N ~ 120. 
 

Como A y B también pueden ser negativos, simplemente extrapolamos el rango y el rango final que obtenemos es [-120, 120].

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to find a pair
// of integers A & B such that
// difference of fifth power is
// equal to the given number X
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find a pair
// of integers A & B such that
// difference of fifth power is
// equal to the given number X
void findPair(int x)
{
    int lim = 120;
 
    // Loop to choose every possible
    // pair with in the range
    for (int i = -lim; i <= lim; i++) {
        for (int j = -lim; j <= lim; j++) {
 
            // Check if equation holds
            if (pow(i, 5) - pow(j, 5) == x) {
                cout << i << ' ' << j << endl;
                return;
            }
        }
    }
    cout << "-1";
}
 
// Driver Code
signed main()
{
    int X = 33;
 
    // Function Call
    findPair(X);
    return 0;
}

// Java implementation to find a
// pair of integers A & B such
// that difference of fifth power
// is equal to the given number X
class GFG{
 
// Function to find a pair
// of integers A & B such that
// difference of fifth power is
// equal to the given number X
static void findPair(int x)
{
    int lim = 120;
 
    // Loop to choose every possible
    // pair with in the range
    for(int i = -lim; i <= lim; i++)
    {
       for(int j = -lim; j <= lim; j++)
       {
            
          // Check if equation holds
          if (Math.pow(i, 5) -
              Math.pow(j, 5) == x)
          {
              System.out.print(i + " " +
                               j + "\n");
              return;
          }
       }
    }
    System.out.print("-1");
}
 
// Driver Code
public static void main(String[] args)
{
    int X = 33;
 
    // Function Call
    findPair(X);
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation to find 
# a pair of integers A & B such 
# that difference of fifth power
# is equal to the given number X
import math
 
# Function to find a pair
# of integers A & B such that
# difference of fifth power is
# equal to the given number X
def findPair(x):
 
    lim = 120
 
    # Loop to choose every possible
    # pair with in the range
    for i in range(-lim, lim + 1):
        for j in range(-lim, lim + 1):
             
            # Check if equation holds
            if (math.pow(i, 5) -
                math.pow(j, 5) == x):
                print (i, end = ' ')
                print (j, end = '\n')
                return
     
    print ("-1")
 
# Driver Code
X = 33
 
# Function Call
findPair(X)
 
# This code is contributed by PratikBasu

// C# implementation to find a
// pair of integers A & B such
// that difference of fifth power
// is equal to the given number X
using System;
 
class GFG{
 
// Function to find a pair of
// integers A & B such that
// difference of fifth power is
// equal to the given number X
static void findPair(int x)
{
    int lim = 120;
 
    // Loop to choose every possible
    // pair with in the range
    for(int i = -lim; i <= lim; i++)
    {
       for(int j = -lim; j <= lim; j++)
       {
           
          // Check if equation holds
          if (Math.Pow(i, 5) -
              Math.Pow(j, 5) == x)
          {
              Console.Write(i + " " +
                            j + "\n");
              return;
          }
       }
    }
    Console.Write("-1");
}
 
// Driver code
public static void Main(String[] args)
{
    int X = 33;
 
    // Function call
    findPair(X);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation to find a
// pair of integers A & B such
// that difference of fifth power
// is equal to the given number X
 
 
// Function to find a pair
// of integers A & B such that
// difference of fifth power is
// equal to the given number X
function findPair(x)
{
    let lim = 120;
 
    // Loop to choose every possible
    // pair with in the range
    for(let i = -lim; i <= lim; i++)
     
    for(let j = -lim; j <= lim; j++)
     
             
        // Check if equation holds
        if (Math.pow(i, 5) -Math.pow(j, 5) == x)
        {
            document.write(i + " "+ j);
            return;
        }
     
    document.write("-1");
}
 
// Driver Code
 
    let X = 33;
 
    // Function Call
    findPair(X);
 
// This code is contributed by mohan
 
</script>

1 -2

Complejidad de tiempo: O (240 * 240)