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
![:-)](./images/smilies/icon_smile.gif)
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![:D](./images/smilies/icon_biggrin.gif)
I have 2 unknown variables & I need 2 equations to determine them while I only have that g * l = a * b.
So
![:D](./images/smilies/icon_biggrin.gif)
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](./images/smilies/icon_biggrin.gif)
---
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: 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".
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: 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![:D](./images/smilies/icon_biggrin.gif)
Hope it will help.
Good luck
![:D](./images/smilies/icon_biggrin.gif)
May be tomorrow is a better day............ ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)