11388 - GCD LCM

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

11388 - GCD LCM

Is it right to say that the solution doesn't exists if and only if G is not a divisor of L?
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
Yes, i think.
if you have 2 numbers a and b... then gcd(a,b)|a and a|lcm(a,b) ( because of the definition of gcd and lcm ).... then this implies gcd(a,b)|lcm(a,b). gl! Eric.

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Re: 11388 - GCD LCM

andmej wrote:Is it right to say that the solution doesn't exists if and only if G is not a divisor of L?
Yes. One way of proving it would be:
if a = product pi ** (alpha i), b = product pi ** (beta i), then
gcd = product pi ** (min(alpha i, beta i)),
lcm = product pi ** (max(alpha i, beta i)).

gcd must divide lcm follows

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
OK, I got Accepted. Thanks. Good problem.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
I'm trying to solve this problem but got WA

I'm using 2 nested loops for a & b, both loops starts from g & ends at l. I did some analysis & figured out that a & b must be in this interval [g, l]. the steps of the 2 loops is also g since I don't need to examine numbers that's not divisable by g. So, whenever I find that GCD(a, b) = g && LCM(a, b) == l, I just break there and that's the solution, else print -1.

I got WA for that. I'm wondering what's wrong ??!!
Is it something wrong with my analysis to the problem (that a & b are in [g, l] & step is g). Or is it just implementation problem ??!!
---
Asmaa Magdi

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
I'm not sure what's wrong with your idea, but I can tell you that you don't need nested loops. There's a simple O(1) solution. Think about it.

Hint: Read carefully the Output part of the problem. There's a very important piece of information there.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
Actually I tried to think of an O(1) algo to solve this problem using just math & just couldn't find any.

I have 2 unknown variables & I need 2 equations to determine them while I only have that g * l = a * b.
So ??!!

I also know that
a % g = 0
& b % g = 0
& l % a = 0
& l % b = 0
but these r not so helpful information. Or at least I'm just missing something here
---
Asmaa Magdi

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
In the problem description it says a must be minimum.

Try to find the solution by hand on paper for some cases, say 5 10, and you will (hopefully) notice the trick.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
Got it ACed but not convinced. Do u have some kind of proof or something ??!!
---
Asmaa Magdi

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
Yes, here's the proof.

What we want to proof is that if it exists a pair of integers (x,y) such that gcd(x,y) = G and lcm(x,y) = L, then the pair in which x is minimum is precisely (G, L).

The interesting problem is when such a pair exists (If it doesn't we print -1). Let's assume the pair exists, and then, we know that x divides y (This was proofed before).

Now, we are trying to show that if x = G, then x is the minimum number that satisfies that gcd(x,y) = G and lcm(x,y) = L. To proof this we will assume that that's not true and reach a contradiction.

Let's suppose that x < G. From the problem description, we know that G >= 1, and then x must be >= 1 too (Since the gcd of x and other integer is >= 1, so x must be at least 1).

We know that gcd(x,y) = G. This implies that G divides x, because of the definition of gcd. Now, since G divides x, it means that x = Gk for some integer k. As stated before, x, G >= 1 and since x is the product of G with some number, we know that k must be at least one (If it was zero or less then x could be zero or less). We have that x is the product of G with a positive integer. This implies that G can't be greater than x, or in other words, G <= x. But this is a contradiction, since we stated that x < G.

Now we have proofed that it's impossible that a pair of (x,y) with x < G satisfies that gcd(x,y) = G. And then, x must be >= G, and the minimum possible value for x is G.

Now we only need to find another integer y such that gcd(G,y) = G and lcm(G,y)=L. But gcd(G,y)lcm(G,y) = Gy (This is a theorem) and as gcd(G,y) = G and lcm(G,y) = L we have that GL = Gy and then y = L.

I hope I've been clear enough.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
Thnx andmej for the proof. I've been so stupid sorry :\$

& I read jvimal post again and got it

Thnx all
---
Asmaa Magdi

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11388 - GCD LCM WA

i think i didnt understand the question correctly
anyway here is my code:

Code: Select all

``````removed
``````
pls help
Last edited by abid_iut on Sun Dec 07, 2008 9:30 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11388 - GCD LCM

I couldnt have found the error.
anyway i solved this problem with three lines.
try to solve in easier way. u can follow the previous post given by "andmej".
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11388 - GCD LCM

hey some one help
I am not sure about the WA
why WA, may be there is a problem for me to understand the problem
here is the code:

Code: Select all

``````Removed after AC
``````
Last edited by abid_iut on Fri Dec 26, 2008 7:58 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 11388 - GCD LCM

Well, your approach is not correct i think. Its a very simple but interesting problem.Just try some test cases in a paper by hand. You should read the previous posts and you will figure out the trick to solve this problem.
Hope it will help.
Good luck
May be tomorrow is a better day............