ALG1701-Editorial

PROBLEM LINK:

Practice

Contest

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.

1 Like

Lol, I remember answering a question on codechef forums which asked about solving this exact same Q (much before this editorial) and XD, I told the approach of GCD there XD.

Nice editorial dear!