возможно ли из a получить b

Question

всем привет, есть два числа, нужно проверить возможно ли получить из числа a другое число b, умножая его на число которое делится на a и посчитать кол-во шагов за которое это можно сделать, например:

a = 2
b = 16

результат такой: 2 --> 4 --> --> 8 -- > 16 ( за 3 шага) в голове нет идей, как это реализовать, пытался через делители числа, но получилось решить только частично. нужна идея для эффективного решения, т.к лимит времени 1.0 сек и ограничение памяти 64мб.

условие задачи тут:

Студенту снится сон. Во сне он ходит по городу, в котором ужасно много трактиров. В каждом трактире выпивает кружку эля. Все трактиры пронумерованы целыми положительными числами, и из трактира с номером n можно пойти только в трактир с номером, который делится на n. Начинается сон в трактире с номером a. Студент знает, что ему надо попасть в трактир с номером b. При этом, понятно, хочет по пути выпить как можно больше эля. Если он не может дойти из трактира a в трактир b, то сразу просыпается в холодном поту.

Answer 1

Если b не делится на a, то добраться из a в b студент не может.

Пусть b делится на a.

Разложим на простые a = p₁^u₁ p₂^u₂ ..., b = p₁^v₁ p₂^v₂ ..., где p_i - все простые числа.

b делится на a, значит ∀ i, u_i ≤ v_i.

Если с между a и b, то a < c < b, a делит c, с делит b. Разложим на простые c = p₁^w₁ p₂^w₂ ...

∀ i, u_i ≤ w_i ≤ v_i

Вместо того чтобы рассматривать делители, будет рассматривать вектора (w_i). Начинается цепочка векторов в (u_i), заканчивается в (v_i). Каждый шаг увеличивает один или несколько элементов w на единицу или больше. Минимальный шаг увеличивает один элемент на единицу. Всего можно сделать шагов ∑_i(v_i - u_i).

Утверждение: число шагов из a в b равно числу шагов из 1 в n (= b / a). Доказательство - почти очевидно.

Программа ниже разлагает n на простые множители и конструирует из них маршрут студента. Сложность O(√(b/a)):

import math


def factors(n):
    i = 2
    j = n
    j_sqrt = math.isqrt(j)
    while i <= j_sqrt:
        if j % i == 0:
            while j % i == 0:
                j //= i
                yield i
            j_sqrt = math.isqrt(j)
        i += 1 if i == 2 else 2
    if j > 1:
        yield j


def steps(a, b):
    p, q = divmod(b, a)
    if q == 0:
        c = a
        yield c
        for f in factors(p):
            c *= f
            yield c



def main():
    s = tuple(steps(*map(int, input().split())))
    print(len(s) - 1, ':', ' -> '.join(map(str, s)))


main()

$ echo 2 144 | python bars.py
5 : 2 -> 4 -> 8 -> 16 -> 48 -> 144

БЛОГ НА HUSL

возможно ли из a получить b

Ответы (1 шт):