Редактировать: я думаю, что это должно быть правильно сейчас.
Этот алгоритм не полагается на факторинг, только на Евклидов алгоритм иего близкий вариант.Это делает его немного более математически сложным, чем решение, использующее факторинг, но оно будет НАМНОГО быстрее.Если вы понимаете Евклидов алгоритм и логарифмы, математика не должна быть проблемой.
(1) Сортировать набор чисел.У вас есть числа вида ab^{n1} < .. < ab^{nk}.
Пример: (3 * 2, 3*2^5, 3*2^7, 3*2^13)
(2) Сформировать новый список, чей n-й элемент (n + 1) -ого элемента отсортированного спискаделится на (п) й.Теперь у вас есть b^{n2 - n1}, b^{n3 - n2}, ..., b^{nk - n(k-1)}.
(продолжение) Пример: (2^4, 2^2, 2^6)
Определить d_i = n_(i+1) - n_i (не программируйте это - вы не могли этого сделать, даже если хотели, так как n_i неизвестны -это просто для того, чтобы объяснить, как работает программа.
(продолжение) Пример: d_1 = 4, d_2 = 2, d_3 = 6
Обратите внимание, что в нашем примере задачи мы можем взять либо (a = 3, b = 2), либо (a = 3/2, b = 4).Суть в том, что любая степень «реального» * 1032 *, которая делит все записи в списке с шага (2), является правильным ответом.Отсюда следует, что мы можем повысить b до любой степени, которая делит все d_i (в данном случае любую степень, которая делит 4, 2 и 6).Проблема в том, что мы не знаем ни b, ни d_i.Но если мы допустим m = gcd(d_1, ... d_(k-1)), то мы МОЖЕМ найти b^m, что достаточно.
ПРИМЕЧАНИЕ: Учитывая b^i и b^j, мы можем найти b^gcd(i, j), используя:
log(b^i) / log(b^j) = (i log b) / (j log b) = i/j
Это позволяет нам использовать модифицированную версию евклидова алгоритма для поиска b^gcd(i, j).«Действие» - все в показателях степени: сложение было заменено умножением, умножением с возведением в степень и (следовательно) частными с логарифмами:
import math
def power_remainder(a, b):
q = int(math.log(a) / math.log(b))
return a / (b ** q)
def power_gcd(a, b):
while b != 1:
a, b = b, power_remainder(a, b)
return a
(3) Поскольку все элементы исходного набора отличаютсяпо степеням r = b^gcd(d_1, ..., d_(k-1)) все они имеют форму cr^n, по желанию.Однако c не может быть целым числом.Дайте мне знать, если это проблема.