11388  GCD LCM
Moderator: Board moderators
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
Are you dreaming right now?
http://www.dreamviews.com
Re: 11388  GCD LCM
Yes. One way of proving it would be:andmej wrote:Is it right to say that the solution doesn't exists if and only if G is not a divisor of L?
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
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
Are you dreaming right now?
http://www.dreamviews.com

 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 ??!!
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
Asmaa Magdi
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.
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
Are you dreaming right now?
http://www.dreamviews.com

 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
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
Asmaa Magdi
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.
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
Are you dreaming right now?
http://www.dreamviews.com

 New poster
 Posts: 27
 Joined: Tue Dec 20, 2005 9:14 am
 Location: Egypt
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.
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
Are you dreaming right now?
http://www.dreamviews.com

 New poster
 Posts: 27
 Joined: Tue Dec 20, 2005 9:14 am
 Location: Egypt
Re: 11388  GCD LCM WA
i think i didnt understand the question correctly
anyway here is my code:
pls help
anyway here is my code:
Code: Select all
removed
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/
http://akanoi.webs.com/

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, 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".
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...............................
It is more tough to become a good person.
I am trying both...............................
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:
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/
http://akanoi.webs.com/

 Learning poster
 Posts: 78
 Joined: Sun Nov 30, 2008 5:00 pm
 Location: IUTOIC, 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
Hope it will help.
Good luck
May be tomorrow is a better day............