C++ 能表示为2的幂的范围内的数字

问题描述包括打印给定范围内可以表示为2的幂的数字的计数，即完全平方数。

所谓完全平方数，是指可以表示为 $x^{y}$ 的数字，其中 $x>0$ 且 $y>1$ 为所有整数。例如，8是一个完全平方数，因为它可以表示为 $2^{3}$ ，等于8，因此被视为完全平方数。

在这个问题中，我们将在输入中获得一个范围作为两个正整数a和b，并且我们的任务是打印在区间[a,b]中存在的完全平方数的数量。

让我们通过以下示例更好地理解这个问题。

输入：

a=1 , b=10

输出

解释 − 在输入中给出了范围[1,10]。我们需要找出这个范围内的完美幂的个数。

$\mathrm{1=1^{2}}$ ，因此它是一个完美幂，因为它可以用 $\mathrm{x^{y}}$ 的形式表示，其中x>0且y>1。

$\mathrm{4=2^{2}}$ ，同样 $x>0$ 且 $y>1$ 。

$\mathrm{8=2^{3}}$

$\mathrm{9=3^{2}}$

因此，范围[1,10[内存在4个完美幂。因此，输出为4。

输入

a=5 , b=20

输出

解释 − 给定的输入是 [5,20]。在给定范围内的完全幂的数量为：

$\mathrm{8=2^{3}}$ ，因为它可以表示为 $\mathrm{x^{y}}$ ，其中 x>0 且 y>1。

$\mathrm{9=3^{2}}$

$\mathrm{16=4^{2}}$

由于给定范围内仅存在3个完全幂，因此所需输出为3。

让我们了解找到给定范围内完全幂数量的算法。

算法

我们知道完全幂是一个可以表示为 $\mathrm{x^{y}}$ 的数字，其中 x>0 且 y>1。由于 C++ 中 long long 数据类型的最大值为 $\mathrm{10^{18}}$ ，存在的完全平方数最多可以到 $\mathrm{10^{9}}$ ，因为大于此数字会导致 long long 数据类型溢出。

在范围内计算完全平方数

对于可以表示为 $\mathrm{x^{y}}$ 的数字，其中 y=2，即给定范围内的完全平方数可以使用给定范围的平方根差来计算。

如果给定范围为[a,b]，则可以使用以下公式计算范围内的完全平方数数量：

范围内的完全平方数数量= floor(sqrtl(b)) − floor(sqrtl(a−1))

floor(x) 函数返回小于或等于传入函数的数值的最大整数。

sqrtl() 用于获取传入数值的平方根，数据类型为 long double。

通过使用上述公式，我们可以得到范围 [a,b] 内的完美平方数总数。我们将 sqrtl(a−1) 包括在内，以包括 a 如果它也是一个完全平方数。

在范围内计算完美幂

现在，对于形如 $\mathrm{x^{y}}$ 的数字，其中 y>=3 且 x>0，我们将只生成具有奇次方的数字，因为偶次方已包含在完全平方数中。

生成奇次方的范围将达到 $\mathrm{10^{6}}$ ，因为该数字的立方将是我们可以存储在 long long 数据类型中的最大值。

所以我们将初始化从i = 2到 $\mathrm{i<10^{6}+1}$ 的for循环，以存储所有可以表示为 $\mathrm{x^{y}}$ 形式的数字，其中y是奇数。我们将初始化一个向量，在每个x的值从2到 $\mathrm{10^{6}}$ 时，存储所有幂大于或等于3且为奇数幂的数字。
我们还将初始化两个集合，一个用于存储完全平方数，另一个用于存储除完全平方数以外的幂。
在for循环中迭代从i = 2到 $\mathrm{10^{6}+1}$ ，并将i的平方值存储在集合中的每个值中。如果i的值已经存在于集合中，我们将继续迭代下一个i的值，因为i是一个完全平方数。任何完全平方数的任意幂也是某个数字的完全平方数。因此，如果i已经存在于集合中，就不会计算i的其他幂，这意味着它是一个完全平方数。
如果i的值不存在于集合中，表示i不是一个完全平方数。因此，我们将通过在while循环中迭代来计算数字的奇数幂。我们将将i的值存储在一个变量中，假设为a，并检查ii $\leq$ 1e18/a。我们将继续将aii的值存储在集合中，并更新a的值为ai*i，并使用while循环中的上述条件存储i的所有奇数幂的值，直到它小于long long数据类型的最大值。

完成迭代后，我们将存储在集合中的所有值存储在我们创建的向量中。我们首先使用集合来存储值，因为它可以存储其中的唯一数字，并且还可以对数字进行排序。

现在，由于我们已经有了所有的完全幂，我们只需使用二分查找来找到在范围内的完全幂数量。

我们将使用以下公式来存储范围内完全平方数的数量 floor(sqrtl(b)) − floor(sqrtl(a−1)) 在给定范围[a，b]的变量中。现在，我们将在c++中使用lower_bound()和upper_bound()函数来查找给定范围内的完全幂数量，并将它们添加到变量中，这将是我们所需的输出。

lower_bound() 函数返回向量中第一个大于或等于传递给函数的数字的位置迭代器。

类似地， upper_bound() 函数返回向量中大于传递给范围的数字的第一个数字的位置迭代器。

如果值不在给定的向量中，它将返回末尾迭代器。

我们将在lower_bound()函数中传递下限a以获取不小于该数字的第一个数字的迭代器。并将上限b传递给upper_bound()函数以获取大于b的第一个数字的迭代器。两者之差将给出给定范围内的完全幂数量。

将给定范围[a，b]中的完全幂数量和完全平方数的数量相加，将给出范围内可以表示为两个数字幂的总数。

我们将在我们的方法中使用算法来解决这个问题。

方法

按照以下步骤来实现我们的方法中的上述算法，以找到在范围内可以表示为两个数的幂的总数：

为了预计算出所有小于1e18的幂，我们将编写一个函数。
在函数中，我们将使用集合将所有小于1e18的幂存储在向量中。
现在，我们将初始化一个变量，其中我们使用公式 floor(sqrtl(b)) – floor(sqrtl(a-1)) 来计算给定范围内的完全平方数的总数。
使用lower_bound()和upper_bound()函数，我们可以得到第一个不小于给定数的迭代器和第一个大于给定数的迭代器。这两者之间的差值将给出给定范围内的完全幂。
将完全平方数的数量加上完全幂的数量将得到在范围内可以表示为两个数的幂的总数，这将是我们的所需输出。

示例

//C++ code to find the total numbers in the range [a,b] which can be expressed as power of two numbers
#include <bits/stdc++.h>

using namespace std;

 long long int n=1000001; //to compute odd powers of numbers until n
 long long int maximum=1e18; //to ensure numbers don't exceed maximum value

set<long long int> sqr; //to store perfect squares
set<long long int> x; //to store odd powers of the number
vector<long long int> p; //to store the values stored in set x

//function to pre calculate all the perfect powers other than perfect squares till 1e18
void PowerCalculation()
{


    for(long long int i=2;i<n;i++)
    {

      long long int t=i*i;
      sqr.insert(t); //store the  square of i in the set

      if(sqr.find(i) !=sqr.end()) //if i is a perfect square, we will continue the loop
      {
          continue;
      }

      long long int val=i; //store i in val if it is not a perfect square
      while(i*i<=maximum/val) //check if i*i is less than or equal to maximum/val to update the next odd power of i in the set
      {
        val=val*i*i; //update val with the next odd power of i
        x.insert(val); //insert the value in the set
      }

    }

    for(auto i:x) //push all the values in the set of perfect powers in the vector
    {
     p.push_back(i); 

    }
}

//function to calculate the total numbers in the range which can be expressed as x^y
long long int perfectPower(long long int start,long long int end)
{
    //to store the number of perfect squares in the range
   long long  int Squares=(floor(sqrtl(end)))-floor((sqrtl(start-1)));

    //to find the index of the first number greater than end
   long long int endPoint = (upper_bound(p.begin(),p.end(), end) - p.begin());

    //to find the first number not less than start
    long long int startPoint = (lower_bound(p.begin(),p.end(), start) - p.begin());

    //adding number of perfect squares and perfect power in the number will give the ans
    long long int ans=Squares+(endPoint-startPoint);

    return ans;
}
int main()
{
    //calling the function to pre calculate odd powers of the number
    PowerCalculation();

   long int start=1;
    long int end=1000000;
   long long int ans=perfectPower(start,end);

   cout<<"The number of Perfect Power is : "<<ans<<endl;

    return 0;
}