資料結構
網路
關係資料庫管理系統 (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 次
