В поисках Венома

Автор задачи и разработчик: Владислав Власов

В каждый момент времени мы имеем прямоугольник со сторонами $$$x$$$ и $$$y$$$, и на каждом шаге из большей стороны вычитается меньшая, то есть если $$$x > y$$$, то совершается переход от пары строн оставшейся области $$$(x, y)$$$ к паре $$$(x - y, y)$$$. Сам же процесс заканчивается, когда $$$x = y$$$ и последним действием сканируется вся оставшаяся область.

Если просто просимулировать этот процесс, как описано в условии, решение, ожидаемо, не пройдёт по времени. Однако можно заметить, что процесс очень похож на поиск НОД двух чисел, то есть алгоритм Евклида.

Быстрый способ провести целиком алгоритм Евклида — заменить вычитание на деление с остатком. В данном случае можно было переходить от пары $$$(x, y)$$$ к паре $$$(y, x \bmod y)$$$, увеличивая при таком действии ответ на $$$\left\lfloor\frac{x}{y}\right\rfloor$$$, так как именно столько вычетаний заменяется одним делением.

Как и алгоритм Евклида, такое решение работает $$$\mathcal{O}(\log(a + b))$$$.