Monitor

Observation 1: normalize the ratio

The requested aspect ratio is $x:y$. But ratios have redundancy: $16:9$ and $1920:1080$ are the same thing.

Let $g = \gcd(x, y), \qquad x' = \frac{x}{g}, \qquad y' = \frac{y}{g}.$ Then $x'$ and $y'$ are coprime.

Now here’s the key number-theory fact:

Any pair of integers $(w, h)$ with ratio $x:y$ must be of the form $w = kx', \qquad h = ky'$ for some integer $k \ge 1$.

Why? Because $\frac{w}{h} = \frac{x}{y} = \frac{x'}{y'}$ with $\gcd(x', y') = 1$. So $w:h = x':y'$, and the only integer pairs with that reduced ratio are common multiples of $(x', y')$.

That’s the whole problem cracked open.

Observation 2: reduction means bounding the multiplier

We are only allowed to reduce the monitor, so the new dimensions must satisfy $w \le a, \qquad h \le b.$ Substitute $w = kx'$ and $h = ky'$: $kx' \le a, \qquad ky' \le b.$ Therefore, $k \le \left\lfloor \frac{a}{x'} \right\rfloor, \qquad k \le \left\lfloor \frac{b}{y'} \right\rfloor.$ So the largest possible valid multiplier is just $k = \min\left(\left\lfloor \frac{a}{x'} \right\rfloor,\; \left\lfloor \frac{b}{y'} \right\rfloor\right).$

Observation 3: maximal area = maximal $k$

The area of the new screen is $A = w \cdot h = (kx')(ky') = k^2 x' y'.$ Since $x'$ and $y'$ are fixed positive constants, maximizing $A$ is exactly the same as maximizing $k$.

So we don’t need binary search, DP, black magic, or a blood sacrifice to the gods of geometry. Just compute the maximum legal $k$.

Edge case

If $k = 0,$ then even the smallest positive screen with this ratio doesn’t fit, so the answer is $0\ 0.$

Otherwise the answer is simply $kx'\ \ ky'.$

Correctness sketch

After reducing $(x, y)$ to coprime $(x', y')$:

1. Every valid integer monitor with ratio $x:y$ has the form $(kx', ky')$.
2. Such a monitor fits iff $kx' \le a$ and $ky' \le b$.
3. Therefore the largest feasible $k$ is $\min\left(\left\lfloor \frac{a}{x'} \right\rfloor, \left\lfloor \frac{b}{y'} \right\rfloor\right).$
4. Area is proportional to $k^2$, so this choice gives the maximum area.

That’s a complete proof. Nice and clean.

Complexity

We only compute one gcd and a few divisions: $O(\log(\min(x,y)))$ for the gcd, and $O(1)$ otherwise.

Memory usage is $O(1).$

With constraints up to $2 \cdot 10^9$, long long is more than enough.