PROBLEM LINK:
Author: Vivek Kumar
DIFFICULTY:
CAKEWALK
PROBLEM:
Cut a paper 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 left over piece of paper.
EXPLANATION:
In the given problem, you have to cut a rectangular paper having size l * b into squares of equal dimension such that no piece of original paper 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 has 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 total number of square of maximum size will be
(l/gcd(l,b))*(b/gcd(l,b))
AUTHOR’S SOLUTION:
Author’s solution can be found here.