Properties of LCM and HCF/GCD:-
Property 1: The product of LCM and HCF of any two given natural numbers is equivalent to the product of the given numbers.
LCM × HCF = Product of the Numbers
Suppose A and B are two numbers, then.
LCM (A & B) × HCF (A & B) = A × B
Property 2: HCF of co-prime numbers is 1. Therefore LCM of given co-prime numbers is equal to the product of the numbers.
LCM of Co-prime Numbers = Product Of The Numbers
Property 3: H.C.F. and L.C.M. of Fractions
LCM of fractions = LCMofnumeratorsHCFofdenominators
HCF of fractions = HCFofnumeratorsLCMofdenominators
GCD and LCM
Two integers A and B are the inputs. Write a program to find GCD and LCM of A and B.
Input
The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer A and B.
Output
Display the GCD and LCM of A and B separated by space respectively. The answer for each test case must be displayed in a new line.
Constraints
- 1 ≤ T ≤ 1000
- 1 ≤ A,B ≤ 1000000
Example
Input
3
120 140
10213 312
10 30
Output
20 840
1 3186456
10 30
#include <iostream>
#define ll long long int
using namespace std;
ll gcd(ll a,ll b)
{
ll i,s,m;
s=(a<b)?a:b;
for(i=s;i>=1;i--)
{
if(a%i==0 && b%i==0)
{
m=i;
break;
}
}
return m;
}
ll lcm(ll a,ll b)
{
ll l,j,n;
l=(a>b)?a:b;
//for l.c.m
for(j=l;j<=a*b;j=j+l)
{
if(j%a==0 && j%b==0)
{
n=j;
break;
}
}
return n;
}
int main()
{
ll t,a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
cout<< gcd(a,b)<<" "<<lcm(a,b)<<endl;
}
return 0;
}
solution:-2
#include <iostream>
#define ll long long int
using namespace std;
ll gcd(ll a,ll b)
{
ll i,s,m;
s=(a<b)?a:b;
for(i=s;i>=1;i--)
{
if(a%i==0 && b%i==0)
{
m=i;
break;
}
}
return m;
}
ll lcm(ll a,ll b,ll g)
{
/* ll l,j,n;
l=(a>b)?a:b;
//for l.c.m
for(j=l;j<=a*b;j=j+l)
{
if(j%a==0 && j%b==0)
{
n=j;
break;
}
}
return n;
*/
return (a*b)/g;
}
int main()
{
ll t,a,b;
cin>>t;
while(t--)
{
cin>>a>>b;
cout<< gcd(a,b)<<" "<<lcm(a,b,gcd(a,b))<<endl;
}
return 0;
}
solution:-3
#include <iostream>
#define ll long long int
using namespace std;
ll gcd(ll a,ll b)
{
if(a==0)
return b;
if(b==0)
return a;
if(a==b)
return a;
if(a>b)
return gcd(a-b,b);
return gcd(a,b-a);
}
ll lcm(ll a,ll b,ll g)
{
return (a*b)/g;
}
int main()
{
ll t,a,b,m,n;
cin>>t;
while(t--)
{
cin>>a>>b;
m=gcd(a,b);
n=lcm(a,b,m);
cout<<m<<" "<<n<<endl;
}
return 0;
}
solution:-4
#include <iostream>
#define ll long long int
using namespace std;
ll gcd (ll a,ll b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
ll lcm (ll a,ll b,ll g)
{
return (a*b)/g;
}
int main()
{
ll t, a , b;
cin>>t;
while(t--)
{
cin >> a >> b;
ll m = gcd ( a, b);
ll n = lcm ( a, b, m);
cout<< m <<" "<< n <<endl;
}
return 0;
}
No comments:
Post a Comment