Números dentro de un rango que se puede expresar como potencia de dos números

Dados dos enteros L y R. Encuentra el número de potencias perfectas en el rango dado [L, R]. Se dice que un número x es potencia perfecta si existen algunos enteros a > 0, p > 1 tales que x = a ^p .

Ejemplos:

Input : 1 4
Output : 2
Explanation : 
Suitable numbers are 1 and 4 where 1
can be expressed as 1 = 12 
and 4 can be expressed as 4 = 22

Input : 12 29
Output : 3
Explanation : 
Suitable numbers are 16, 25 and 27.

Requisitos previos: comprobar si un número se puede expresar como x^y , búsqueda binaria y potencia perfecta (1, 4, 8, 9, 16, 25, 27, …)

Planteamiento: Arreglemos algo de energía p. Es obvio que no hay más de 10 ^18/p números x tales que x ^p no exceda 10 ¹⁸ para un p en particular. Al mismo tiempo, sólo para p = 2 esta cantidad es relativamente grande, para todos los demás p ≥ 3 la cantidad total de tales números será del orden de 10 ⁶ . Hay 10 ⁹ cuadrados en el rango [1, 10 ¹⁸ ], por lo que no podemos almacenarlos para responder a nuestra consulta.

O bien, genere todas las potencias para p ≥ 2 y elimine todos los cuadrados perfectos entre ellos o genere solo potencias impares de números como 3, 5, 7, etc. Luego, la respuesta a la consulta (L, R) es igual a la cantidad de generado números entre L y R más algunos cuadrados perfectos en el rango.

1. El número de cuadrados perfectos en el rango es la diferencia del valor mínimo de la raíz cuadrada de R y el valor mínimo de la raíz cuadrada de (L – 1), es decir ( suelo (raíz cuadrada (R)) – suelo (raíz cuadrada (L – 1) Tenga en cuenta que , debido a problemas de precisión, el sqrt estándar puede producir valores incorrectos, por lo tanto, utilice la función de búsqueda binaria o sqrtl incorporada definida en cmath (Consulte aquí para obtener más descripción de sqrtl).
2. Para generar esos extraños poderes de los números. En primer lugar, realice un cálculo previo para encontrar números que puedan expresarse como potencias de algún número hasta 10 ¹⁸ para que podamos responder muchas consultas y no sea necesario procesarlas una y otra vez para cada consulta. Comience iterando un ciclo de 2 a 10 ⁶ (ya que estamos calculando para potencias p ≥ 3 y 10 ⁶ es el número máximo cuya potencia elevada a 3 no puede exceder 10 ¹⁸ ), para cada valor insertamos su cuadrado en un conjunto y verificamos además, si ese valor ya es un cuadrado perfecto (ya presente en el conjunto), no encontramos otras potencias de ese número (ya que cualquier potencia de un cuadrado perfecto es también un cuadrado perfecto). De lo contrario, ejecute un ciclo interno para encontrar potencias impares del número hasta que exceda 10¹⁸ e inserte en otro conjunto diga ‘s’. Con este enfoque, no hemos empujado ningún cuadrado perfecto en el conjunto ‘s’.

Por lo tanto, la respuesta final sería la suma del número de cuadrados perfectos en el rango y la diferencia del valor superior de R y el valor inferior de L (utilizando la búsqueda binaria).
A continuación se muestra la implementación del enfoque anterior en C++.

// CPP Program to count the numbers
// within a range such that number
// can be expressed as power of some
// other number
#include <bits/stdc++.h>
  
using namespace std;
  
#define N 1000005
#define MAX 1e18
  
// Vector to store powers greater than 3
vector<long int> powers;
  
// set to store perfect squares
set<long int> squares;
  
// set to store powers other
// than perfect squares
set<long int> s;
  
void powersPrecomputation()
{
    for (long int i = 2; i < N; i++) 
    {
        // pushing squares
        squares.insert(i * i);
  
        // if the values is already
        // a perfect square means
        // present in the set
        if (squares.find(i) != squares.end())
                continue;
  
        long int temp = i;
  
        // run loop until some
        // power of current number
        // doesn't exceed MAX
        while (i * i <= MAX / temp) 
        {
            temp *= (i * i);
  
            /* pushing only odd powers
            as even power of a number
            can always be expressed as 
            a perfect square which is
            already present in set squares  */
            s.insert(temp);
        }
    }
  
    // Inserting those sorted 
    // values of set into a vector
    for (auto x : s)
        powers.push_back(x);
}
  
long int calculateAnswer(long int L, long int R)
{
    // calculate perfect squares in 
    // range using sqrtl function
    long int perfectSquares = floor(sqrtl(R)) - 
                            floor(sqrtl(L - 1));
  
    // calculate upper value of R 
    // in vector using binary search
    long int high = (upper_bound(powers.begin(), 
            powers.end(), R) - powers.begin());
  
    // calculate lower value of L 
    // in vector using binary search
    long int low = (lower_bound(powers.begin(),
            powers.end(), L) - powers.begin());
  
    // add into final answer
    perfectSquares += (high - low);
  
    return perfectSquares;
}
  
// Driver Code
int main()
{
    // precompute the powers
    powersPrecomputation();
  
    // left value of range
    long int L = 12;
      
    // right value of range
    long int R = 29;
  
    cout << "Number of powers between " << L 
            << " and " << R << " = " << 
            calculateAnswer(L, R) << endl;
  
    L = 1;
    R = 100000000000;
  
    cout << "Number of powers between " << L
            << " and " << R << " = " << 
            calculateAnswer(L, R) << endl;
  
    return 0;
}

Number of powers between 12 and 29 = 3
Number of powers between 1 and 100000000000 = 320990