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}
$$
Let's analyze a single case:
If we want to cover a $6x5$ rectangle with $7$ squares, we first note that each square at most has an area of $30/7$. We also know that for our filling to be optimal, we need to fill at least an axis.
So now we know that we will fill either the $6$ or the $5$ completely. We will first try with the 5. Since the maximal side of our squares is $\sqrt{30/7}$, we now need the smallest integer more than $5/\sqrt{30/7}$, that is equal to $\lceil5/\sqrt{30/7}\rceil=3$
So we would divide the $5$ in $3$ parts $p_x$, so each side will have $5/3$ . If so, I would cover $(5/3)^2*7=19\frac49$ of the thirty squares. If they don't fit vertically, we try with more parts $p_x$, until the squares fit in the other axis. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$
Also, since $p_x$ is integer $\lfloor p_x \rfloor =p_x$
If we do the same with the $6$, we get $\lceil6/\sqrt{30/7}\rceil$ again covering $19\frac49$ of the surface. We then do the same as with the $5$ and save it as $p_y$
Let's now recall the formulas we had.
We had an $x∗y$ rectangle and filled it with $N$ squares. We started with $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ or $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ and then we made them fit by shrinking them until they fit in the other axis. But we know we want the area maximised, so $Side=max(x/p_x,y/p_y)$.
A better method:
Once we have the start value $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,if it does not fit in the $y$ axis, we need to make it fit in the $y$ axis. For that, we use that
$$a=x/p_x$$
where $a$ is the value of the actual side of our squares.
Then we know that for our side to fit we need to reduce it:
$$S_x=y/(\lceil y/a \rceil)$$
We do the same with $S_y$ and calculate $max(S_x,S_y)$
The advantage of this is that it needs a constant number of operations, the most expensive one being the square root.
Plain, unoptimized C Code
Some multiplications may be reused but for code readability and practical uses this is enough.
Input: values of $x$,$y$, and $n$. Handcoded.
Output: The optimal side of our squares
#include <math.h>
#include <stdio.h>
#define MAX(x,y) (x)>(y)?(x):(y)
int main(){
double x=5, y=6, n=7;//values here
double px=ceil(sqrt(n*x/y));
double sx,sy;
if(floor(px*y/x)*px<n) //does not fit, y/(x/px)=px*y/x
sx=y/ceil(px*y/x);
else
sx= x/px;
double py=ceil(sqrt(n*y/x));
if(floor(py*x/y)*py<n) //does not fit
sy=x/ceil(x*py/y);
else
sy=y/py;
printf("%f",MAX(sx,sy));
return 0;
}
Best Answer
Suppose you have a rectangle $w$ units wide and $h$ units high, and you place $2\times2$ squares in this rectangle. Wherever there is an edge of any of these squares parallel to the bottom edge of the rectangle, extend that edge into a line all the way across the rectangle. In this way you will divide the entire rectangle into horizontal strips of which parts are covered by parts of the $2\times2$ squares and parts are not. In the figure below, $2\times2$ squares have been placed in a $9\times7$ rectangle. The red lines cut the rectangle into strips of $9$ units from left to right and various distances from bottom to top.
In this example the squares appear to be placed somewhat haphazardly, but no matter how you place the squares, you cannot make more than $4$ squares overlap any of the horizontal strips. In general, if the width of the rectangle is $w,$ you can make at most $\lfloor w/2 \rfloor$ of the $2\times2$ squares overlap each strip.
This means that each horizontal strip contains at least $w_2\Delta h$ area that is not covered by the $2\times2$ squares, where $w_2 = (w - 2\lfloor w/2 \rfloor)$ and $\Delta h$ is the height of each strip. (Some of the strips have an even larger area uncovered.) If we add up the uncovered area over all the strips, we find that an area measuring at least $w_2 h$ is uncovered.
Similarly, if we cut the rectangle into vertical strips by extending every vertical edge of every square, we find that each strip has at least $h_2 \Delta w$ uncovered area, where $h_2 = (h - 2\lfloor h/2 \rfloor)$ and $\Delta w$ is the width of the strip. Adding this up, we find that an area of at least $h_2 w$ is uncovered.
These two uncovered regions overlap, but only to a limited extent, namely a total area of $(2\lfloor w/2 \rfloor)(2\lfloor h/2 \rfloor) = (w - w_2)(h - h_2).$ The total uncovered area comes out to $$ w_2 h + h_2 w - (w - w_2)(h - h_2) = wh - w_2 h_2. $$
This is the same as you get if you simply arrange the $2\times2$ squares in an array $\lfloor w/2 \rfloor$ squares across and $\lfloor h/2 \rfloor$ squares high in the lower left corner of the rectangle. That is to say, we have just shown (in a rigorous, though long-winded way) that the best arrangement of the squares is just to stack them in continuous rows, leaving a gap (if necessary) along two edges of the rectangle.
The total number of squares in the array fitted in this way is $\lfloor w/2 \rfloor \times \lfloor h/2 \rfloor.$
If we generalize this to $N\times N$ squares in a $w\times h$ rectangle, the maximum number of squares of that size is $\lfloor w/N \rfloor \times \lfloor h/N \rfloor.$