[InterviewBit] 2つの整数の累乗

Question

これは質問です： 32ビット符号付き整数に収まる正の整数を与えれば、P> 1かつA> 0のA^Pで表すことができます。 Pは両方とも整数でなければなりません。

私はブルートフォース方式で解決できることを知っています。しかし、私はそれをより良い方法で解くことができるかどうか、あるいは再帰技法を使って解くことができますか？ ご協力ありがとうございます！

Answer 1

一つのアプローチは、doubleに変換し、1/log2 nに1/2、1/3、1/4、というように、最高の端数の力を得るために数学を使用することです。結果はAになります。小数部の分母はPとなります。

電力の計算はdouble秒であるため、ceilとfloorの両方を実行する必要があります。結果を見つけずにゼロに達すると、アルゴリズムが停止する可能性があります。 Nは、ちょうど1除数を持っている場合

Answer 2

は、初期整数N.

ファーストを呼び出すことができます、あなたはそれが形D^Kであるので、それはだと、N.

のすべての素因子を取得する必要があります本当。

1つ以上の除数がある場合は、各除数の数字の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 

Answer 3

これはまた、この方法で解決することができます。

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 4

1. == 1が、それは、X^0したがって 真として表すことができるならば、我々はチェックします。 a> 1の場合、2または3または4のいずれかをチェックします。 pが2であるか、3であるか、または4であるかどうかをp（p == 1）とすると、pが0であることを意味する。 、......。 p （p = a）はx^yと書くことができます。従って真を返す。

---

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; 

    }