Can anyone discuss mentioned problem solution? I can’t understand the accepted soln of peoples.

Problem link : Contest Page | CodeChef

Can anyone discuss mentioned problem solution? I can’t understand the accepted soln of peoples.

Problem link : Contest Page | CodeChef

You have to find the square of greatest side length that can be formed from rectangle n*m.

Since you have to cut the rectangle in squares of some length L, L must be divisible by n and m.

And since we need to find maximum L, the L should be the GCD Of n and m.

Therefore total squares possible =

n*m/(gcd(n,m)*gcd(n,m))

In code the solution would be (FOR C++)

```
#include bits/stdc++.h
#define int long long
signed main
{
int t;
std::cin >> t;
while(t--)
{
int l, b;
std::cin >> l >> b;
int g = __gcd(l, b);
int ans = (l*b)/(g*g);
std::cout << ans << std:: endl;
}
}
```