两个整数的幂

Question

这是一个问题：给定一个适合32位有符号整数的正整数，找出它是否可以表示为a^P，其中P>1和a>0。A和P都应该是整数。

我知道我可以用蛮力的方法解决它；然而，我想知道我是否可以用一种更好的方法来解决它，或者我可以使用递归技术来解决它？谢谢你的好心帮助！

Answer 1

一种方法是转换为double，并使用数学来获得1/2、1/3、1/4等的分数幂，直到1/log2 n。结果将是A；该分数的分母将是CCD_ 7。

由于功率的计算是以doubles为单位的，因此需要同时尝试结果的ceil和floor。一旦你在没有找到结果的情况下达到零，算法可能会停止。

Answer 2

这也可以通过这种方式解决。

public boolean isPower(int a) {
    if (a == 1) return true;
    for (int idx = 2; idx * idx <= a; idx ++) {
        double val = Math.log (a)/Math.log (idx);
        if ((val - (int) val) < 0.00000001) return true;
    }
    return false;
}

Answer 3

1. 我们将检查如果a==1，那么它可以表示为x^0，因此是的。对于>1，我们将检查2或3或4….a；我们会的如果p%2或，3或，4或……，则除以p(p=a(。。。。。。。如果(p==1(意味着p是完全可被2，或3，或4整除。表示p(其中p=a(我们可以写成x^y，因此返回true

---

 public boolean isPower(int a) {
       if(a==1) return true;
         for (int i = 2; i*i <= a; i++) {
              int p = a;
              while(p%i == 0){
                p/=i;
              }
              if(p == 1) return true;
         }
         return false;
  }

Answer 4

基于@xenteros Answer和成功提交的代码。

public static int isPower(int A) {
        if(A == 1)
            return 1;
        double Ad = A ;
       for(int i =2;i<=(Math.log(Ad)/Math.log(2));i++)
       {
           double a = Math.pow(Ad,(double)1/i);
           if(Math.ceil(a) == Math.floor(a) || Math.ceil(a)-a <0.000000001)
                return 1;
       }
       return 0;
    }

Answer 5

while(test--)
{
    int input;
  cin>>input;
  if(input<=2)
  {cout<<"0"<<endl;
  break;}
  //cout<<m;
  int m=sqrt(input);
  int count=2;
  int flag=0;
while(count<=m+1)
{
    if(ceil(log2 (input)/log2 (count))== floor(log2 (input)/log2 (count)))
    {
       // cout<<"ghusa   "<<count<<"  "<<input;
        flag=1;
        cout<<"1";
        break;
    }
    count++;
}
if(flag==0)
{cout<<"0";
}
cout<<endl;  
}
return 0;

}

Answer 6

bool ans(long long int n)
{
    if(n==1)
        return true;
    else
    {
        for (long long int i = 2; i*i <= n; i++)
        {
            if(ceil(log2 (n)/log2 (i)) == floor(log2 (n)/log2 (i)))
            {
                return true;
            }
        }
    }
    return false;
}

Answer 7

让我们调用初始整数N。

首先，你必须得到N.的所有素数

如果N只有1个除数，它的形式是D^k，所以它是真的。

如果它有一个以上的除数，你应该检查每个除数的gcd是否与1不同，并且是偶数。

例如：

12 = 2 * 2 * 3
not possible, GCD(2,1) = 1
24 = 2 * 2 * 2 * 3
not possible, GCD(3,1) = 1
36 = 2 * 2 * 3 * 3
possible,     GCD(2,2) = 2
144 = 2 * 2 * 2 * 2 * 3 * 3
possible,     GCD(4,2) = 2
120 = 2 * 2 * 2 * 3 * 5
not possible, GCD(1,1,3) = 1
216 = 2 * 2 * 2 * 3 * 3 * 3
not possible, GCD(3,3) = 3