数据结构
网络
关系数据库管理系统 (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 次浏览
