# ZACKHAN - Editorial

Contest

Practice

Easy

GCD

### PROBLEM:

We are given the length and the breadth of rectangular shaped cloth out of which, we are required to cut square shaped handkerchieves. The task is to compute the maximum side length of the square shaped handkerchieves.

### QUICK EXPLANATION:

The maximum side length can be calculated by computing the GCD of the given length(L) and breadth(B).

### EXPLANATION:

We have to find the maximum number of square-shaped handkerchiefs of maximum size possible out of a given cloth material. Here, L and B are the length and breadth of the given cloth material respectively. Now, we have to divide it in square-shaped divisions such that these are the maximum size possible per piece. Which, in this case, will be calculated by finding the Greatest Common Divisor (GCD) of L and B of the given piece of cloth.
For Example,
For a piece of cloth of L= 30 and B=40, the size of maximum square-shaped handkerchiefs possible can be found out by calculating the GCD of its length and breadth which is 10. So, the maximum length of square-shaped handkerchiefs possible is 10 units.

### AUTHOR’S AND TESTER’S SOLUTIONS:

The solution can be found here

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n–)
{
int l,b;
cin>>l>>b;
cout<<__gcd(l,b)<<endl;
}
}

#include
using namespace std;
void hcf(int a, int b) // a<=b
{
int r,q,m;

do{
m = a; // to store the last non-zero value of r
r = b%a;
q = b/a;
b = a;
a = r;

}while(r!=0);

``````cout<<m;
``````

// else hcf(r,a);
//return 0;
}
int main()
{
cout<<"hcf of 10 and 15 = ";
hcf(10,15);
}

//