Пусть первая сторона нового монитора (изначально $a$) равна $a^{\prime }$, тогда вторая сторона равна $b^{\prime }=\frac{y}{x}\times a$. Следовательно чем больше возьмём $a$ тем больше будет другая сторона, а следовательно площадь монитора будет тоже больше. Напишем бинпоиск по $a^{\prime }$. К сожалению $\frac{y\times a^{\prime }}{x}$ не всегда целое число(.

Давайте это исправим. Для этого разделим $x$ и $y$ на $gcd(x,y)$. Получаем, что дробь $\frac{y}{x}$ не сократима. Значит $\frac{y\times a^{\prime }}{x}$ целое в том случае, если $\frac{a^{\prime }}{x}$ целое число.

Пусть такое $a^{\prime }$ найдено. Тогда $a^{\prime }=x\times C$, где $C$ целое число. Тогда $b^{\prime }=\frac{y\times a^{\prime }}{x}=\frac{y\times \left(x\times C\right)}{x}=y\times C$.

Получаем :

$$a^{\prime }=C\times x$$

$$b^{\prime }=C\times y$$

Сделаем бинпоиск по $C$. Будем проверять, что $a^{\prime }\le a$ и $b^{\prime }\le b$. Асимптотика решения $O(\log 10^9)$.

На самом деле получить $C$ можно гораздо проще. Достаточно проверить два максимальных случая, когда $C\times x\le a$ и $C\times y\le b$. $C=min(x//a,b//y)$, где $//$ деление нацело.