Please Help Me To Solve This Problem ( Related to Math )

general
1

Problem link:- PrepBytes

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()
{
  //write your code here
  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;
}
2

Overflow is not uncommon for such kinds of problems.

Consider this input.

Input

1
999999883 999999893 999999929 999999937

Expected Output

999999812000008307 1

Your Output

8882398262143807441 -999999830000006741

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

CPP 
/**
 * Author: Sai Suman Chitturi
 * Powered By: GitHub Copilot
 */

#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
3

Thanks for the help :smile:

4

Thank you Sir , for the solution . Through this I learned about cpp_int . :smile: