Theatre Square

Key observation

This problem is almost insultingly simple once you stop overthinking it.

You have a rectangle of size $n \times m$, and square tiles of size $a \times a$.

• Tiles cannot be broken.
• Tiles must stay parallel to the square.
• It’s okay if they stick out past the border.

That means coverage in the two dimensions is completely independent.

Reduce to one dimension

Suppose you only want to cover a segment of length $n$ using pieces of length $a$. How many do you need?

You need the smallest integer $k$ such that

$k \cdot a \ge n.$

That is exactly

$k = \left\lceil \frac{n}{a} \right\rceil.$

Same logic for the other side:

$\left\lceil \frac{m}{a} \right\rceil.$

Total number of flagstones

Since each tile occupies one “row slot” and one “column slot”, the total number is

$\left\lceil \frac{n}{a} \right\rceil \cdot \left\lceil \frac{m}{a} \right\rceil.$

That’s it. No DP, no geometry wizardry, no sacrifice to the gods of Codeforces.

Integer ceiling trick

Do not use floating point here. There’s zero reason to invite precision weirdness to a kindergarten math problem.

For positive integers,

$\left\lceil \frac{x}{a} \right\rceil = \frac{x + a - 1}{a}$

using integer division.

So:

$\text{rows} = \frac{n+a-1}{a}, \qquad \text{cols} = \frac{m+a-1}{a}.$

Then

$\text{answer} = \text{rows} \cdot \text{cols}.$

Important implementation detail

The constraints go up to $10^9$. The answer can be as large as roughly

$10^9 \cdot 10^9 = 10^{18},$

so int is not enough. Use long long.

Complexity

The algorithm is constant time:

$O(1)$

with

$O(1)$

extra memory.

Short, clean, and brutally effective.