两个整数的幂
Power Of Two Integers
我正在尝试解决有关两个整数的幂的问题。问题描述如下:
Given a positive integer which fits in a 32 bit signed integer, find
if it can be expressed as A^P where P > 1 and A > 0. A and P both
should be integers.
Example:
Input: n = 8
Output: true
8 can be expressed as 2^3
Input: n = 49
Output: true
49 can be expressed as 7^2
现在,我已经按照下面的方法解决了这个问题。
int Solution::isPower(int A) {
if(A == 1)
{
return true;
}
for(int x = 2; x <= sqrt(A); x++)
{
unsigned long long product = x * x;
while(product <= A && product > 0)
{
if(product == A)
{
return true;
}
product = product * x;
}
}
return false;
}
但是,我从 geeksforgeeks 中找到了另一个解决方案,它仅使用对数除法来确定该值是否可以用两个整数的幂表示。
bool isPower(int a)
{
if (a == 1)
return true;
for (int i = 2; i * i <= a; i++) {
double val = log(a) / log(i);
if ((val - (int)val) < 0.00000001)
return true;
}
return false;
}
谁能解释一下上面的对数解法?提前致谢。
它正在使用数学来解决这个问题。
9=3^2
Log 9 = log 3^2... Adding log at both side
Log 9 = 2 * log 3...using log property
2 = log 9 / log 3
如你所见,最后一条语句等同于代码
双 val = log(a) / log(i);
然后它检查 Val - round(val) 是否为 0...如果这是真的,val 就是 ans 否则它不会是 0。对数不给出精确的 ans。
我正在尝试解决有关两个整数的幂的问题。问题描述如下:
Given a positive integer which fits in a 32 bit signed integer, find if it can be expressed as A^P where P > 1 and A > 0. A and P both should be integers.
Example:
Input: n = 8
Output: true
8 can be expressed as 2^3Input: n = 49
Output: true
49 can be expressed as 7^2
现在,我已经按照下面的方法解决了这个问题。
int Solution::isPower(int A) {
if(A == 1)
{
return true;
}
for(int x = 2; x <= sqrt(A); x++)
{
unsigned long long product = x * x;
while(product <= A && product > 0)
{
if(product == A)
{
return true;
}
product = product * x;
}
}
return false;
}
但是,我从 geeksforgeeks 中找到了另一个解决方案,它仅使用对数除法来确定该值是否可以用两个整数的幂表示。
bool isPower(int a)
{
if (a == 1)
return true;
for (int i = 2; i * i <= a; i++) {
double val = log(a) / log(i);
if ((val - (int)val) < 0.00000001)
return true;
}
return false;
}
谁能解释一下上面的对数解法?提前致谢。
它正在使用数学来解决这个问题。
9=3^2
Log 9 = log 3^2... Adding log at both side
Log 9 = 2 * log 3...using log property
2 = log 9 / log 3
如你所见,最后一条语句等同于代码 双 val = log(a) / log(i);
然后它检查 Val - round(val) 是否为 0...如果这是真的,val 就是 ans 否则它不会是 0。对数不给出精确的 ans。