Page 1 of 2

11388 - GCD LCM

Posted: Sat Jan 12, 2008 8:31 pm
by andmej
Is it right to say that the solution doesn't exists if and only if G is not a divisor of L?

Posted: Sat Jan 12, 2008 8:34 pm
by sonyckson
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.

Re: 11388 - GCD LCM

Posted: Sat Jan 12, 2008 8:45 pm
by jvimal
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 :-)

Posted: Sat Jan 12, 2008 10:15 pm
by andmej
OK, I got Accepted. Thanks. Good problem.

Posted: Sun Mar 02, 2008 11:40 pm
by asmaamagdi
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 ??!!

Posted: Sun Mar 02, 2008 11:59 pm
by andmej
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.

Posted: Mon Mar 03, 2008 12:12 am
by asmaamagdi
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 :D ??!!

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 :D

Posted: Mon Mar 03, 2008 12:58 am
by andmej
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.

Posted: Mon Mar 03, 2008 1:49 am
by asmaamagdi
Got it ACed but not convinced. Do u have some kind of proof or something ??!!

Posted: Mon Mar 03, 2008 4:44 am
by andmej
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.

Posted: Mon Mar 03, 2008 1:04 pm
by asmaamagdi
Thnx andmej for the proof. I've been so stupid sorry :$

& I read jvimal post again and got it :D

Thnx all

Re: 11388 - GCD LCM WA

Posted: Sat Nov 22, 2008 8:23 pm
by abid_iut
i think i didnt understand the question correctly
anyway here is my code:

Code: Select all

removed
pls help

Re: 11388 - GCD LCM

Posted: Sun Nov 23, 2008 4:10 am
by kbr_iut
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".

Re: 11388 - GCD LCM

Posted: Sun Dec 07, 2008 9:29 pm
by abid_iut
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

Re: 11388 - GCD LCM

Posted: Mon Dec 08, 2008 6:36 pm
by Articuno
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 :D