时间戳

首页 > 解决方案 > 两个整数的幂

c++ - 两个整数的幂

问题描述

我正在尝试解决有关两个整数的幂的问题。问题描述如下：

给定一个适合 32 位有符号整数的正整数，找出它是否可以表示为 A^P，其中 P > 1 和 A > 0。A 和 P 都应该是整数。
示例：
输入：n = 8
输出：true
8 可以表示为 2^3

输入：n = 49
输出：true
49 可以表示为 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; 
}

谁能解释一下上述对数解决方案？提前致谢。

标签： c++algorithmlogarithm

解决方案

它正在使用数学来解决这个问题。

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

如您所见，最后一条语句等效于代码 double val = log(a) / log(i);

然后它检查 Val - round(val) 是 0 ...如果那是真的 val 是 ans 否则它不会是 0。对数不给出精确的 ans。

推荐阅读