Given a rectangle of sides $m$ and $n$. $( m,n \in [1,1000] )$ We can
cut the rectangle into smaller identical pieces such that each piece
is a square having maximum possible side length with no left over
piece of the rectangle. How could we count this squares of maximum
size?
For example: If the rectangle is of size $6 \times 9$. We can cut it into 54 squares of size $1 \times 1$, $0$ of size $2 \times 2$, $6$ of size $3 \times 3$, $0$ of size $4 \times 4$, $0$ of size $5 \times 5$ and $0$ of size $6 \times 6$. The minimum number of squares of maximum size that can cut is $6$.
My approach: I computed the product $m \times n$ say $K$.Then found the maximum perfect square that divides $K$. The quotient of this division seems to be the required answer. But unfortunately it's doesn't seem to yield correct answer. Where exactly I am going wrong?
Best Answer
You want to cut the rectangle in squares with side length $s$ without pieces of the rectangle left over, so $s$ must divide both $m$ and $n$. The maximum possible value of $s$ is thus the greatest common divisor of $m$ and $n$: $$s = \gcd(m,n)$$
To find the number of squares the rectangle is cut into, you need to find how many squares fit in the length of the rectangle $\left(\frac{m}{\gcd(m,n)}\right)$ and multiply that with the amount of squares that fit in the width of the rectangle $\left(\frac{n}{\gcd(m,n)}\right)$:
$$ \left(\frac{m}{\gcd(m,n)}\right) \times \left(\frac{n}{\gcd(m,n)}\right) = \frac{m \times n}{\gcd(m,n)^2} $$