数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究可在表示为两个数的幂的范围内表示的数字
问题陈述包括打印给定范围内可以表示为两个数的幂的数字的数量，即完全幂的数字。
被称为完全幂的数字是可以表示为$\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() 用于获取以 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 是奇数。我们将初始化一个向量来存储所有幂大于或等于 3 且对于从 2 到$\mathrm{10^{6}}$的每个 x 值都是奇数幂的数字。
我们还将初始化两个集合来存储完全平方数，第二个集合存储除完全平方数之外的幂。
在从 i=2 到$\mathrm{10^{6}+1}$的 for 循环中迭代，并将每个值的 i 的平方存储在集合中。如果 i 的值已存在于集合中，我们将继续迭代下一个 i 值，因为 i 是一个完全平方数。任何完全平方数的任何次幂也是某个数字的完全平方数。因此，如果 i 已存在于集合中，这意味着它是完全平方数，我们将不计算 i 的其他幂。
如果 i 的值不存在于集合中，这表明 i 不是完全平方数。因此，我们将通过在 while 循环中迭代来计算数字的奇数幂。我们将 i 的值存储在一个变量中，例如 a，并检查 i*i <= 1e18/a。我们将继续将 a*i*i 的值存储在集合中，并使用上述条件在 while 循环中更新 a 的值，直到它小于 long long 数据类型的最大值。
完成迭代后，我们将把存储在集合中的所有值存储在我们创建的向量中。我们首先使用集合来存储值，因为它存储其中的唯一数字，并且它也存储排序的数字。
现在，由于我们拥有所有完全幂的数字，我们将简单地使用二分查找来查找给定范围内的完全幂的个数。
我们将使用公式floor(sqrtl(b)) − floor(sqrtl(a−1))在给定范围 [a,b] 中的一个变量中存储完全平方数的个数。现在，我们将使用 c++ 中的 lower_bound() 和 upper_bound() 函数来查找给定范围内的完全幂的个数，并将它们添加到变量中，这将是我们所需的输出。
lower_bound() 函数返回向量中第一个不小于函数中传递的数字的迭代器。
同样，upper_bound() 函数返回向量中第一个大于范围中传递的数字的迭代器。
如果该值不在给定向量中，则返回 end 迭代器。
我们将向量的下界 a 传递给 lower_bound() 函数以获取第一个不小于该数字的迭代器。并将上界 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;
}
输出
The number of Perfect Power is : 1111
结论
本文讨论了查找范围内可以表示为两个整数幂的总数的问题。我们预计算了所有完全幂，这使我们能够在 C++ 中以$\mathrm{O(logN)}$ 的运行时间查找范围内是完全幂的总数。
我希望在阅读本文后，您能更好地理解解决这个问题的概念和方法。
浏览量 190 次
