# Someone please explain me the logic behind this problem.

To answer this question, first you need to find the largest X such that squares of side X can exactly fit into a rectangle of sides M, N.

The following are some important observations:

1. The squares should exactly fit inside the rectangle. Therefore, M and N both should be divisible by X.
2. As the number of squares should be minimum, the side of the squares i.e. X has to be maximised.

From the above, it is clear that the required X is the GCD of M and N.

Finally, we have to find the number of squares of side X that fit into a rectangle of sides M, N. This is

``(Area of rectangle) / (Area of one square) = (M * N) / (X * X)``
2 Likes

Thanks…

#include<stdio.h>
int main()
{

int i,n,N,M,T,j;
scanf("%d",&T);

for(j=0;j<T;j++)
{ int max=1;
scanf("%d%d",&N,&M);
n=NM;
for(i=1;(i
i)<n;i++)
{
if(n % (ii)==0)
max=i;
}
printf("%d\n",n/(max
max));

}

``````return 0;
``````

}

The logic is simple.

First, lets take a look at problem. It says that “So your task is to find the minimum number of square plots that can be formed out of the rectangular plot.”

Firstly, we see that its a rectangular field and secondly, the number of square must be MINIMUM. (So thinking that M*N squares of 1x1 area is solution is wrong.) In other words, problem is asking us the MINIMUM number of squares (of greatest X which fits) which will fit in the rectangle.

Now, first thing. Area of Rectangle is MN.
Area of square is X
X

Firstly, the solution is integral. ==>M*N must be divisible by X^2 (or X square, as we say).

Also, since square is inside the rectangle, ==> X <= min(M,N) (since if X is more than length or breadth, then it wont fit)

Lets say that the answer is m. ==> m * XX= MN
Thus, m= (MN)/(XX)
(in last para I will prove that this equation is further constrained to m = (M/X) * (N/X) where M/X AND N/X MUST BE integers.)
and m is minimum, and integral.

Many algos come to mind.

The best one is, as the first answer told, Is finding the GCD. In case you need code, PM me. Notice that it is a compulsory condition that length%x==0 AND breadth%x==0. To explain it, allow me to take a test case-