PROBLEM LINK:CodeChef: Practical coding for everyone
Author: Abhishek Yadav
Tester: Abhishek Yadav
Editorialist: Abhishek Yadav
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
Sachin has a rectangular Sheet of paper for his regular rough work. Sachin comes to know that he will get more space to do rough work if he cuts the rectangular sheets into square shapes.
So keeping this in mind, he decides to divide his rectangular sheet into minimum possible number of square sheet papers, such that each square sheet has the same area, and the square sheets divide the rectangular one perfectly.
So your task is to find the minimum number of square sheets with the same area, that can be formed out of the rectangular sheet, such that they divide it perfectly.
QUICK EXPLANATION:
Should contain concise explanation, clear to advanced coders.
EXPLANATION:
If you read the question carefully then you will find that this is a “GCD” finding problem.
As we have to divide the rectangular sheet into minimum possible number of square sheets which means we have to find the “gcd” of length and breadth.
Now if GCD is equal to 1, then we get our answer as L x B because we can divide the sheet into only L x B square sheet.
if gcd is greater then one then we have to simply divide the l*b by square of GCD
[ i.e:- answer= ( ( L x b) / (gcd x gcd ) ) ].
where L and B are Length and breadth respectively.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int T,N,M,k,r;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>N>>M;
k=__gcd(N,M);
r=(NM)/(kk);
cout<<r<<endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int T,N,M,k,r;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>N>>M;
k=__gcd(N,M);
r=(NM)/(kk);
cout<<r<<endl;
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int T,N,M,k,r;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>N>>M;
k=__gcd(N,M);
r=(NM)/(kk);
cout<<r<<endl;
}
return 0;
}