Автор задачі: | Микола Арзубов |
Задачу підготував: | Данило Квіт |
Розбір написав: | Костянтин Денисов |
Нехай та — це сторони прямокутника, які ми шукаємо. Очевидно, що виконується рівність 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}.