Problem Statement for FoxAndGCDLCM

Problem Statement      Fox Jiro and Eel Saburo are good friends. One day Saburo found two interesting positive integers: A and B. On the next day, Saburo met Jiro and wanted to tell him the two integers. However, he managed to forget their values. All Saburo could remember was their greatest common divisor G and their least common multiple L. You are given two longs: G and L. Find the original integers A and B, and return the value of A+B. If there are multiple pairs of A and B that correspond to G and L, pick the one that minimizes A+B. If it is impossible to find such A and B (i.e., Saburo made a mistake somewhere), return -1.   Definition      Class: FoxAndGCDLCM Method: get Parameters: long, long Returns: long Method signature: long get(long G, long L) (be sure your method is public)        Notes - The greatest common divisor of two integers a and b is the largest positive integer that divides both a and b without any remainder. - The least common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b.   Constraints - G will be between 1 and 1,000,000,000,000 (10^12), inclusive. - L will be between 1 and 1,000,000,000,000 (10^12), inclusive.   Examples 0)      2 20 Returns: 14 The possible pairs of A and B are {2, 20} and {4, 10}. We need to pick {4, 10} since 4+10 is the smallest sum of A and B. 1)      5 8 Returns: -1 There are no pairs of A and B such that their greatest common divisor is 5 and their least common multiple is 8. 2)      1000 100 Returns: -1 3)      100 1000 Returns: 700 4)      10 950863963000 Returns: 6298430 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior       The key point behind this question is prodect(AB)=gcd*lcm. Now since the number crosses        10^12 which means gcd*lcm may excedd the bound. So first inference if (lcm%gcd!=0) then there is no pair A and B. Now first we divide lcm/gcd let the value be temp. Now the numbers should be such that when  multiplied gives temp and is coprime to each other. We choose such A,B such that A+B is minimised. The answer is (A+B)*gcd.                ******** Code goes here *************** #include<bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define ss second #define ff first #define ll long long int #define inf 5000000000000000000 ll get(ll g, ll l) {   if(l%g!=0)   return -1;   ll val=l/g;   ll temp=sqrt(val);   ll mi=inf;   for(int i=1;i<=temp;i++)   {                if(val%i==0)                {                       ll f1=i;     ll f2=val/i; if(__gcd(f1,f2)==1) {        mi=min(inf,f1+f2); }  }     }   return mi*g; } int main() {  ll g,l;  cin>>g>>l;  cout<<get(g,l)<<endl;  return 0; }