PROBLEM LINK:
PRACTICE
Editorialist: Avishake Maji
DIFFICULTY:
Medium
PREREQUISITES:
Maths, Number theory
PROBLEM:
Chef meets his friend Rohan after a long time. Rohan is quite good at maths. He gives some problems to Chef. Since Chef is weak in maths he wants your help. You have to find the sum of three numbers such that lcm of first two numbers and last two numbers are given. These three numbers are pairwise distinct and also co prime to one other.
Input:
t: no of test cases
m,n: lcm of first two numbers and last two numbers respectively
Output:
Sum of three numbers
Constraints:
1<=t<=1000
1<=m,n<=10000
Sample Input:
2
6 15
35 77
Sample Output:
10
23
EXPLANATION:
We are told to find the sum of three numbers where the lcm of first two and last two numbers are given. To solve this problem we find to find the hcf of the two lcms. Then we have to add (lcm of first two numbers)/hcf +hcf+(lcm of last two numbers)/hcf .
SOLUTION:
#include <iostream>
#include<ctime>
#include<map>
#define ll long long int
using namespace std;
void solve();
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("error.txt", "w", stderr);
// freopen("output.txt", "w", stdout);
// #endif
int t;
/*is Single Test case?*/ cin >> t;
while (t--) {
solve();
// cout << "\n";
}
// cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
ll gcd(ll a,ll b){
if(b>a)
swap(a,b);
while(a%b!=0){
ll r=a%b;
a=b;
b=r;
}
return b;
}
void solve()
{
ll a,b;
cin>>a>>b;
ll p=gcd(a,b);
cout<<(a/p)+p+(b/p)<<endl;
}