Проверьте, является ли одно целое число целой степенью другого

Question

Это вопрос для интервью : «Учитывая 2 целых числа x и y, проверьте, является ли x целой степенью y» (например, для x = 8 и y = 2 ответ «true» а для х = 10 и у = 2 «ложь»).

Очевидное решение:

int n = y; while(n < x) n *= y; return n == x

Теперь я думаю о том, как его улучшить.

Конечно, я могу проверить некоторые особые случаи: например, x и y должны быть нечетными или четными числами, то есть мы можем проверять младший значащий бит x и y. Однако мне интересно, смогу ли я улучшить сам алгоритм ядра.

Answer 1

Я нашел это решение // Проверьте, можно ли выразить A как степень двух целых чисел

    int isPower(int A)
    {
     int i,a;
     double p;
     if(A==1)
     return 1;
     for(int a=1; a<=sqrt(A);++a )
     {
         p=log(A)/log(a);
         if(p-int(p)<0.000000001)
         return 1;
     }
    return 0;
   }

binarycoder.org

Answer 2

Если у вас есть доступ к наибольшему значению y, которое может быть встроено в требуемый тип данных, это действительно удобный способ решения этой проблемы.

Допустим, в нашем случае y == 3.Итак, нам нужно проверить, является ли x степенью 3.

. Учитывая, что нам нужно проверить, является ли целое число x степенью 3, давайте начнем думать об этой проблеме в терминахиз того, какая информация уже имеется.

1162261467 - это наибольшая степень 3, которая может вписаться в Java int.1162261467 = 3^19 + 0

Данный x может быть выражен как [(a power of 3) + (some n)].Я думаю, что это довольно элементарно, чтобы иметь возможность доказать, что если n равно 0 (что случается , если x является степенью 3), 1162261467 % x = 0.

Итак, чтобы проверить, является лиданное целое число x является степенью три, проверьте, если x > 0 && 1162261467 % x == 0.

Обобщение.Чтобы проверить, является ли данное целое число x степенью данного целого числа y, проверьте, является ли x > 0 && Y % x == 0: Y наибольшей степенью y, которая может вписаться в целочисленный тип данных.

Общая идея заключается в том, что если A - это некоторая степень Y, то A можно выразить как B/Ya, где a - некоторое целое число и A < B.Он следует точно такому же принципу для A > B.Дело A = B элементарно.