[InterviewBit] Сила двух целых чисел

Question

это вопрос: Приведенное положительное целое число, которое вписывается в 32-битное целое число со знаком, найдет, если оно может быть выражено как A^P, где P> 1 и A> 0. A и P оба должны быть целыми числами.

Я знаю, что могу решить его с использованием метода грубой силы; однако, мне интересно, смогу ли я решить его лучше, или я могу решить его с помощью техники рекурсии? Спасибо за вашу любезную помощь!

Answer 1

Один подход заключается в преобразовании в double и использовать математику, чтобы получить дробных степеней 1/2, 1/3, 1/4, и так далее, вплоть до 1/log2 n. Результатом будет A; знаменатель фракции будет P.

Поскольку расчет мощности находится в double с, вам нужно попробовать как ceil, так и floor результата. Как только вы нажмете нуль, не найдя результата, алгоритм может остановиться.

Answer 2

Назовём начального число N.

Во-первых, вы должны получить все простые делители N.

Если N имеет только один делитель, что он находится в виде D^к, так что правда.

Если у него более 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, то он может быть представлен в виде х^0, следовательно, истинной. при a> 1 мы будем проверять либо 2 или 3, либо 4 .... a; разделите p (p = a), если p% 2 или, 3 или, 4 или ......., если (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; 

    }