Area of the Cake#377

Area of the Cake (Editorial)

Автор задачі:

Микола Арзубов

Задачу підготував:

Данило Квіт

Розбір написав:

Костянтин Денисов

Нехай та — це сторони прямокутника, які ми шукаємо. Очевидно, що виконується рівність a \cdot b = P + Q. Це означає, що і є дільниками числа x := P + Q. Усі дільники числа можна знайти за O(\sqrt{x}) операцій.

Розглянемо кожен дільник числа . Для нього перевіряємо, чи підходить прямокутник зі сторонами та \frac{x}{d}. Тобто, якщо двоє людей почнуть відрізати від такого прямокутника найбільші можливі квадрати, ми можемо обчислити площі цих квадратів і порівняти їх із та .

Щоб обчислювати площі швидко, зауважимо, що прямолінійне віднімання меншої сторони від більшої може бути дуже повільним. Наприклад, якщо c = 1 і d = 10^12, знадобиться 10^12 операцій.

Однак можна скористатися ефективнішим підходом. Помітимо, що менша сторона змінюється лише тоді, коли більша сторона зменшується до d \mod c. За один такий перехід виконується \lfloor \frac{d}{c} \rfloor операцій. Цей підхід аналогічний алгоритму Евкліда для знаходження найбільшого спільного дільника (НСД) двох чисел, який працює за O(\log{\min(a, b)}).

Таким чином, загальна складність алгоритму становить O(\sqrt{P + Q} \cdot \log{(P + Q)}). На практиці алгоритм працює ще швидше, оскільки кількість дільників числа значно менша за \sqrt{P + Q}.