資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學完全冪（1, 4, 8, 9, 16, 25, 27, …）
完全冪是一個自然數，它是相等自然數因子的乘積。它也可以定義為可以表示為另一個大於一的整數的平方冪或更高冪的整數。
例如，4 可以表示為 2*2 的乘積。
27 可以表示為 3*3*3 的乘積。因此，4 和 27 是完全冪。
問題陳述
給定一個數字 n，找出小於或等於 n 的完全冪的個數。
示例 1
Input = 14 Output = 3
解釋
1 = 1*1.
4 = 2*2.
9 = 3*3.
因此，1、4 和 9 是小於 14 的完全冪。
示例 2
Input = 27 Output = 7
解釋
1 = 1*1.
4 = 2*2.
9 = 3*3.
16 = 4*4.
25 = 5*5.
27 = 3*3*3.
因此，1、4、9、16、25 和 27 是小於等於 27 的完全冪。
方法 1：暴力法
此方法涉及計算從 1 到 n 的平方根的所有整數冪。這意味著對於每個基數（值為 1 到 n 的平方根），我們將計算具有基數的平方、基數的立方、基數的四次方等等的數字。
虛擬碼
Start
For 1<= i <=sqrt(n)
j = i^2
While j <= n:
j = j*i
Increase count
End
示例
下面是一個 C++ 程式，用於計算型別為 xy（其中 x>0 且 y>1）且小於 n 的完全冪數。
#include <bits/stdc++.h>
using namespace std;
// Function to find all perfect power numbers less than n
int perfectPower(int n){
// answer is going to store all power numbers
// creating a set to store the unique values
set<int> answer;
answer.insert(1);
// Iterating for base number i, from 2 to square root of n
for (long long i = 2; i * i <= n; i++) {
// starting from i squared
long long j = i * i;
answer.insert(j);
// Increasing the power of base till its <= n
while (j * i <= n) {
// going to next power of i
answer.insert(j * i);
j = j * i;
}
}
// returning the size of set as it has no duplicates
return answer.size();
}
// Driver Code
int main(){
int n = 50;
cout<< "Number of perfect powers less than or equal to 50:" << endl;
cout << perfectPower(n);
return 0;
}
輸出
Number of perfect powers less than or equal to 50: 10
將元素插入集合的時間複雜度為 O(log n)，最多可以插入 n 個元素。
因此，時間複雜度為 O(n log n)
集合的最大大小可以是 n。因此，空間複雜度為 O(n)
方法 2
在最後一種方法中，我們計算了從 2 到 n 的平方根的基數的所有冪。
在這種方法中，我們將奇數冪與偶數冪分開，並分別計算它們的個數。
為了計算小於等於 n 的所有偶數冪，我們只需要 n 的平方根。因為小於 n 的偶數冪的個數等於 n 的平方根。
證明
小於等於 25 的偶數冪 = 1、4、9、16、25，共有 5 個整數。
9 = 1, 4 , 9
為了計算奇數冪：我們將使用上述方法中使用的函式。
我們將找到大於 2 且小於 n 的立方根的所有可能的冪。
然後，計算奇數值。這可以透過檢查該值是否是偶數冪來檢查，如果是偶數冪，則它將具有整數平方根。
此外，除了使用集合之外，另一個選擇是使用向量，但是向量需要排序並刪除任何被推入向量的重複項。
虛擬碼
Start
For 1<= i <=cube root(n)
J = i^2
While j <= n:
J = j*i
If j is not a perfect square
Increase count
end
示例
下面是一個 C++ 程式，用於計算型別為 xy（其中 x>0 且 y>1）且小於等於 n 的完全冪數。
#include <bits/stdc++.h>
using namespace std;
// Function to find all perfect power numbers less than n
int perfectPower(int n){
// answer is going to store all power numbers
vector<int> answer;
// Iterating for base number i, from 2 to cube root of n
for (long long i = 2; i * i * i <= n; i++) {
// starting from i square
long long j = i * i;
// increase the power of j till it is <= n
while (j * i <= n) {
j *= i;
// only adding those values of j which
// don't have a integral square root
long long s = sqrt(j);
if (s * s != j)
answer.push_back(j);
}
}
// sorting the vector and removing all the duplicate values
sort(answer.begin(), answer.end());
answer.erase(unique(answer.begin(), answer.end()), answer.end());
// Num of even powers is equal to the square root of n.
int numOfEven = (long long)sqrt(n);
// Returning number of odd and even powers
return answer.size() + numOfEven ;
}
int main(){
// Function call
cout<< "Number of perfect powers less than or equal to 10:" << endl;
int ans = perfectPower(10);
// Printing the answer
cout << ans;
return 0;
}
輸出
Number of perfect powers less than or equal to 10: 4
時間複雜度將由排序向量決定，即 O(n log n)
時間複雜度：O(n log n)
空間複雜度：O(n^(1/4))。因為我們只儲存小於 n 的奇數冪
結論
在本教程中，我們解決了計算小於或等於給定數字 n 的完全冪的問題。
我們討論了兩種方法：
找到所有可能的冪，直到 n 的平方根。
將解決方案分成兩部分，並使用小於 n 的偶數冪的個數等於 n 的平方根這一事實。並手動計算奇數冪以節省時間並提供空間最佳化的解決方案。
947 次瀏覽
