Not able to understand the solution of a simple math problem

Question

I was practicing the following beginner level problem at codechef

Santosh has a farm at Byteland. He has a very big family to look after. His life takes a sudden turn and he runs into a financial crisis. After giving all the money he has in his hand, he decides to sell some parts of his plots. The speciality of his plot is that it is rectangular in nature. Santosh comes to know that he will get more money if he sells square shaped plots. So keeping this in mind, he decides to divide his plot into minimum possible square plots so that he can get maximum profit out of this.

So your task is to find the minimum number of square plots that can be formed out of the rectangular plot.

Input

The input consists of T number of test cases. T lines follow. Each line consists of two integers N and M which denotes the length and breadth of the rectangle.

Output

Output is a single line which denotes the minimum number of square plots that can be formed

Constraints

1<=T<=20
1<=M<=10000
1<=N<=10000

Input:

2

10 15

4 6

Output:

6

6

My approach was there could be large number of possible small squares as there are squares of size 1, 2, 3, 4, ..., min(length, breadth).

So I would sum them up.

But when I went through the other people solutions, all of them are doing it as follows:

$$ans = \frac{(length*breadth)}{\gcd(length*breadth)^2}$$

Can anyone explain me how the above equation is an answer to the given problem and how is it derived. The reason why am I asking for help is I just don't want to copy paste or memorize this formula, rather I want to understand the steps how they came to this equation OR it is a standard formula which I am yet unaware of.

Any help is much appreciated.

Answer 1

There is an error that probably you made transcribing the formula used by the other people, it should be

$$\rm ans = \frac{length \times breath}{\gcd(length, breath)^2 }$$

Notice that the $\gcd$ function in the denominator is doing anything useful only when applying it to $2$ or more operands, not to just one as you did above.

That formula is the solution to a slightly different problem than stated, namely when all the plots of land not only have to be square, but also the same size. Maybe that was the intention of the problem, but it certainly is not stated.

For example, for $\rm length = 3, breath = 4$, that formula says the answer is $12$, which amounts to getting $12$ $1\times1$ plots. Of course, you can devide this area into 4 squares: one is $3 \times 3$, the other 3 are $1 \times 1$.

That the given formula is a solution to the altered problem is easy to so, as the common side length of the small square plots needs to divide both the breath and the length of the original farm. The greatest values to do that (which produces the smallest number of plots) is the gcd of both values.

That means you get $\rm \frac{length}{gcd(length, breath)}$ small plots in the length direction of the farm and $\rm \frac{breath}{gcd(length, breath)}$ small plots in the breath direction. Multiply both values and you get the formula above.

The problem you tried to solve (allowing different sizes of plots) may be very hard or very easy (just get the biggest square possible from the remaining farm, the continue recursivly), I'm not sure.

Answer 2

The answer makes sense if all square plots must be the same area.

In that case, note that $MN$ is the total area of the rectangle, and $\gcd(M,N)$ is the maximum side length of a square which can tesselate the rectangle. Thus, the number of square plots total is $MN/\gcd(M,N)^2$, and this is minimized when the square's side length is maximized.

To see why the maximum side length of square plots is $\gcd(M,N)$, first assume you tiled the entire plot with squares of side length $x$. Now suppose $x$ is not a common divisor of $M$ and $N$, so either $x \nmid M$ or $x \nmid N$. WLOG let $x \nmid M$; then, we can write $M = qx + r$ for some $0 < r < m$. You cannot tesselate the $M$ by $N$ rectangle with only $x$ by $x$ squares since there would be $r$ units of length remaining in the plot, and that remaining area is too narrow to be tiled by $x$ by $x$ squares. By contradiction, $x$ must be a common divisor of $M$ and $N$. Since choosing the greatest common divisor leads to the fewest square plots, that is the optimal choice.