一定范围内可以表示为2的幂的数
问题描述包括打印给定范围内可以表示为2的幂的数的数量，即完全幂的数。
被称为完全幂的数是可以表示为$\mathrm{x^{y}}$的数，其中对于所有整数，x>0，y>1。例如，8 是一个完全幂，因为它可以表示为 $\mathrm{2^{3}}$，等于 8，因此它被认为是一个完全幂。
在本题中，输入两个正整数 a 和 b，我们的任务是输出 [a,b] 区间内完全幂的数量。
通过以下示例更好地理解这个问题。
输入
a=1 , b=10
输出
4
解释- 输入中给出了区间 [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
输出
3
解释- 给出的输入是[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 ([a,b])，则可以使用以下公式计算该范围内的完全平方数:
范围内的完全平方数= floor(sqrtl(b)) − floor(sqrtl(a−1))
floor(x) 函数返回函数中小于或等于传入数字的最大整数。
sqrtl() 用于计算传入数字的平方根，该数字为长整型双精度数。
使用上述公式，我们可以得到 [a,b] 范围内完全平方数的总数。如果 a 也是完全平方数，我们取 sqrtl(a−1) 来包含它。
计算范围内的完全幂
现在，对于形式为 $\mathrm{x^{y}}$ 的数字，其中 y>=3 且 x>0，我们将只生成奇数幂的数字，因为偶数幂包含在完全平方数中。
奇数幂的生成范围最高可达 $\mathrm{10^{6}}$，因为该数的立方是 long long 数据类型所能存储的最大值。
因此，我们将初始化一个从 i=2 到 $\mathrm{i<10^{6}+1}$ 的 for 循环，用于存储所有可以表示为 $\mathrm{x^{y}}$ 形式的数，其中 y 为奇数。我们将初始化一个向量，用于存储所有幂大于或等于 3 的数，并且对于从 2 到 $\mathrm{10^{6}}$ 的每个 x 值，向量都是奇数幂。
我们还将初始化两个集合，分别用于存储完全平方数和除完全平方数之外的幂。
使用 for 循环从 i=2 迭代到 $\mathrm{10^{6}+1}$，并存储集合中每个值的 i 的平方。如果 i 的值已存在于集合中，我们将继续迭代查找下一个 i 的值，因为 i 是一个完全平方数。任何完全平方数的任意次幂也是某个数的完全平方数。因此，如果 i 已存在于集合中，即 i 是一个完全平方数，我们就不会计算 i 的其他次幂。
如果 i 的值不存在于集合中，则说明 i 不是完全平方数。因此，我们将通过 while 循环迭代计算该数的奇数次幂。我们将 i 的值存储在变量 a 中，并检查 i*i 是否 <= 1e18/a。我们将不断将 a*i*i 的值存入集合中，并用 a*i*i 更新 a 的值，进一步存储所有 i 的奇数次幂的值，直到它小于 long long 数据类型的最大值，在 while 循环中使用上述条件。
迭代完成后，我们将集合中的所有值存储在我们创建的向量中。我们首先使用集合来存储这些值，因为它存储唯一数字，并且存储已排序的数字。
现在，由于我们已经拥有所有完全幂数，因此我们将使用二分查找来查找范围内完全幂数的数量。
我们将使用公式 floor(sqrtl(b)) − floor(sqrtl(a−1)) 将完全平方数的数量存储在给定范围 [a,b] 内的变量中。现在我们将使用 C++ 中的 lower_bound() 和 upper_bound() 函数来查找给定范围内完全幂的数量，并将它们添加到变量中，该变量将作为我们所需的输出。
lower_bound() 函数返回向量中第一个不小于函数传入数字的迭代器。
类似地，upper_bound() 函数返回向量中第一个大于范围传入数字的迭代器。
如果该值不在给定的向量中，则返回最终迭代器。
我们将在 lower_bound() 函数中传递下限 a，以获取向量中第一个不小于该数字的迭代器。在 upper_bound() 函数中传递上限 b，以获取第一个大于 b 的数字的迭代器。两者之差将得出给定范围内完全幂的数量。
将给定范围 [a,b] 内的完全幂和完全平方的数量相加，将得出该范围内可以用两个数的幂表示的总数。
我们将在我们的方法中使用算法来解决这个问题。
方法
在我们的方法中，为了找到范围内可以用两个数的幂表示的总数，需要遵循以下步骤:
为了预先计算 1e18 以内的所有完全幂，我们将编写一个函数。
在函数中，我们将使用集合将 1e18 以内的所有完全幂存储在向量中。
现在，我们将初始化一个变量，使用以下公式将给定范围内的完全平方总数添加到该变量中floor(sqrtl(b)) − floor(sqrtl(a−1))。两个数的平方根之差将得出其平方和在给定范围内的总数。
使用 lower_bound() 和 upper_bound() 函数，我们可以分别获取第一个不小于该数和第一个大于该数的数处的迭代器。这两个函数之差将得出给定范围内的完全幂。
将完全幂中的完全平方数相加，将得出该范围内的总数，这些总数可以表示为两个数的幂，这就是我们所需的输出。
示例
//C++ 代码用于查找 [a,b] 范围内可以表示为两个数的幂的总数
#include <bits/stdc++.h>
using namespace std;
long long int n=1000001; //计算数字的奇数幂，直到 n
long long int maximum=1e18; //确保数字不超过最大值
set<long long int> sqr; //存储完全平方数
set<long long int> x; //存储数字的奇数幂
vector<long long int> p; //存储集合 x 中的值
//函数用于预先计算除完全平方数之外的所有完全幂，直到 1e18
void PowerCalculation()
{
for(long long int i=2;i<n;i++)
{
long long int t=i*i;
sqr.insert(t); //将 i 的平方存入集合
if(sqr.find(i) !=sqr.end()) //如果 i 是完全平方数，则继续循环
{
continue;
}
long long int val=i; //如果 i 不是完全平方数，则将 i 存入 val
while(i*i<=maximum/val) //检查 i*i 是否小于或等于 maximum/val，以更新集合中 i 的下一个奇数次幂
{
val=val*i*i; //将 val 更新为 i 的下一个奇数次幂
x.insert(val); //将值插入集合
}
}
for(auto i:x) //将完美幂集的所有值推送到向量中
{
p.push_back(i);
}
}
//函数用于计算范围内可以表示为 x^y 的总数
long long int perfectPower(long long int start,long long int end)
{
//存储范围内完全平方数的数量
long long int Squares=(floor(sqrtl(end)))-floor((sqrtl(start-1)));
//查找第一个大于 end 的数字的索引
long long int endPoint = (upper_bound(p.begin(),p.end(), end) - p.begin());
//查找第一个不小于 start 的数字
long long int startPoint = (lower_bound(p.begin(),p.end(), start) - p.begin());
//将完全平方数和完全幂相加，得到答案
long long int ans=Squares+(endPoint-startPoint);
return ans;
}
int main()
{
//调用函数预先计算数字的奇数次方
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;
}
输出
The number of Perfect Power is : 1111
结论
本文讨论了如何找出可用两个整数的幂表示的范围内所有数字的总数。我们预先计算了所有完全幂，这使得我们能够在 C++ 中以 $\mathrm{O(logN)}$ 的运行时间找到范围内所有完全幂的数字。
希望您阅读本文后能更好地理解该概念以及解决问题的方法。
