DIFFICULTY:
Easy
PREREQUISITES:
Properties of GCD(Greatest Common Divisor)
PROBLEM:
Alice and Bob are childhood friends. Due to COVID-19, the government imposed lockdown across the country. So, they have a limited quantity of food with them. In food, they have only bread of size l x b. So, they decided to cut bread into identical pieces such that each piece is square. Alice decided that she will take the square having maximum possible side length as she does some workout so she needs more energy.
Note: There will be no leftover piece of bread.
EXPLANATION:
Cut a bread of size l * b into smaller identical pieces such that each piece is a square of the same dimension and having maximum possible side length with no leftover piece of bread.
APPROACH:
In the given problem, you have to cut a rectangular bread having size l * b into squares of equal dimension such that no piece of original bread is left over. So we have to make cuts only vertically or horizontally. Hence we can conclude that if the length of a side of the square is a, both l and b both have to be divisible by a.
Now, there’s another constraint. a has to be as large as possible.
The problem reduces to finding an integer whose value is maximum as well as divisible by both l & b which is equivalent to finding the greatest common divisor (gcd) of l & b.
So the total number of square of maximum size will be
(l/gcd(l,b))*(b/gcd(l,b))
TIME COMPLEXITY:
T*(log(l)+log(b))
Where
T: number of test cases,
l: length of the rectangle,
b: width of the rectangle.
SOLUTIONS:
Setter's Solution
import sys
def gcd(a,b):
if a==0 :
return b
if b==0 :
return a
else :
return gcd(b,a%b)
t = int(raw_input())
i = 0
for i in range(0,t):
a,b = map(int,sys.stdin.readline().split())
print (a*b)/(gcd(a,b)*gcd(a,b))