 My Approach :-

1. lcm of a/b and c/d is (product of both)/(gcd of both)

2. To find lcm of two fractions we have to find gcd
of those fractions.

formula to find gcd of (a/b) and (c/d) is :-
gcd(a,c)/lcm(b,d)

1. Suppose we get pro1/pro2 as ( product of both )
and gcd1/gcd2 as ( gcd of both )

2. Lcm of two fraction = (pro1 * gcd2)/(pro2 * gcd1)
let us consider it as lcm1/lcm2
Now to reduce it into simplest form we can devide lcm1 and
lcm2 with the gcd(lcm1,lcm2)

My Code :-

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll findGCD(ll a,ll b)
{
if(a==0)
return b;
return findGCD(b%a,a);
}

ll findLCM(ll a,ll b)
{
ll gcd=findGCD(a,b);
return((a*b)/gcd);
}

int main()
{
int t ; cin>>t;

for(int i=0;i<t;i++)
{
ll a,b,c,d; cin>>a>>b>>c>>d;

ll gcd=findGCD(a,c);
ll lcm=findLCM(b,d);

ll gcd1=gcd;
ll gcd2=lcm;

//cout<<" gcd1/gcd2 "<<gcd1<<"/"<<gcd2<<endl;

ll pro1=a*c;
ll pro2=b*d;

ll final_num=(pro1*gcd2);
ll final_den=(pro2*gcd1);

//cout<<"final_num and final_den "<<final_num<<" "<<final_den<<endl;

ll final_divisor=findGCD(final_num,final_den);

cout<<final_num/final_divisor<<" "
<<final_den/final_divisor<<endl;

}

return 0;
}

Overflow is not uncommon for such kinds of problems.

Consider this input.

Input

1
999999883 999999893 999999929 999999937

Expected Output

999999812000008307 1

8882398262143807441 -999999830000006741

Here’s my code (not sure if it actually passes other test cases)

CPP
/**
* Author: Sai Suman Chitturi
*/

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using namespace boost::multiprecision;

static inline cpp_int gcd(cpp_int a, cpp_int b) {
for(cpp_int rem = 0; b > 0; rem = a % b, a = b, b = rem);
return a;
}

static inline cpp_int lcm(cpp_int a, cpp_int b) {
return (a / gcd(a, b)) * b;
}

void solve() {

cpp_int a = 0, b = 0, c = 0, d = 0;
cin >> a >> b >> c >> d;

cpp_int den = lcm(b, d);

cpp_int A = a * (den / b);
cpp_int C = c * (den / d);

cpp_int num = lcm(A, C);
cpp_int reducer = gcd(num, den);

num /= reducer;
den /= reducer;

cout << num << ' ' << den << '\n';
}

int main() {
int t = 0;
cin >> t;
for(; t > 0; t--) {
solve();
}
return 0;
}

3 Likes

Thanks for the help Thank you Sir , for the solution . Through this I learned about cpp_int . 