GcD LCM help question

https://www.codechef.com/ENAU2019/problems/LGCD please explain

Find all the pairs of the type (a,2a) using a map. That is the solution .

4 Likes

But why…how u observe that can u prove it mathematically
Q. Is just (a * b) = 2 * (gcd(a,b)2)

1 Like

LCM OF (A,2A) IS ALWAYS 2A
GCD OF (A,2A) IS ALWAYS A
HENCE 2A =2×A

No i understand that , but how u think in contest by just observing , or on paper , i need som another proof, don’t mind @anon55659401 help

2 Likes

Yes… (20 characters)

1 Like

We will be uploading the editorials shortly. :blush:

1 Like

You are right but I think it comes from experience and practise …

yeah i completely agree on your point but sometimes u have to know things with proof also , bcz when i explain to other person , i have to give some proof

Proof :
lcm(a,b) = 2*gcd(a,b)
lcm(a,b)*gcd(a,b) = 2*gcd(a,b)*gcd(a,b)
a*b=2*gcd(a,b)*gcd(a,b)
As,
a= k1*gcd(a,b) and b=k2*gcd(a,b)
where k1,k2>0 and integer
Now a*b= k1*k2*gcd(a,b)*gcd(a,b) = 2*gcd(a,b)*gcd(a,b)
Since 2 is prime,
which implies k1=1 and k2=2 or k2=1 and k1=2
it implies that a=2*b or b=2*a

6 Likes

ok let’s extend this
a∗b=X * (gcd(a,b))^Y)
now it implies that
a = X * b^(Y-1) … right means in array if a is present then X * a^(Y-1) must be prsent to satisfies above condition
for ex:
X =3 Y =4
then a * b = 3 * GCD(a , b) ^ 4 , we want.
now if in array “2” is present then " 3 * (2 ^(4-1)) = 3*(2^(3)) = 3*8 = 24 " must presnt

1 Like

Awesome , that’s what i want , thanks bro :slight_smile:

2 Likes

This is correct ?? @l_returns

1 Like

I don’t understand. Buts let’s extend it after someone asks this extension in a contest :stuck_out_tongue:

Oh …k no worry yesterday after contest over and seeing solution i extend this and observe but again fail to prove mathematically,
But is this correct or not … tell me
PS : Have u give Kickstart 2019 Round E

1 Like

Thank you so much @l_returns for explaining :blush:. I really love your explanation :heart:

3 Likes

Thanks a lot :slight_smile: \hspace{0mm}

1 Like

Thanx for huge response and clearing doubts …

1 Like