### 11388 - GCD LCM

Posted:

**Sat Jan 12, 2008 8:31 pm**Is it right to say that the solution doesn't exists if and only if

**G**is not a divisor of**L**?The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=41&t=27309

Page **1** of **2**

Posted: **Sat Jan 12, 2008 8:31 pm**

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**

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.

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.

Posted: **Sat Jan 12, 2008 8:45 pm**

Yes. One way of proving it would be:andmej wrote:Is it right to say that the solution doesn't exists if and only ifGis not a divisor ofL?

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**

OK, I got Accepted. Thanks. Good problem.

Posted: **Sun Mar 02, 2008 11:40 pm**

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 ??!!

Posted: **Sun Mar 02, 2008 11:59 pm**

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**

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

Posted: **Mon Mar 03, 2008 12:58 am**

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.

Posted: **Mon Mar 03, 2008 1:49 am**

Got it ACed but not convinced. Do u have some kind of proof or something ??!!

Posted: **Mon Mar 03, 2008 4:44 am**

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**) = G**y** (This is a theorem) and as gcd(G,**y**) = G and lcm(G,**y**) = L we have that GL = G**y** 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 (

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

Now, we are trying to show that if

Let's suppose that

We know that gcd(

Now we have proofed that it's impossible that a pair of (

Now we only need to find another integer

I hope I've been clear enough.

Posted: **Mon Mar 03, 2008 1:04 pm**

Thnx andmej for the proof. I've been so stupid sorry :$

& I read jvimal post again and got it

Thnx all

& I read jvimal post again and got it

Thnx all

Posted: **Sat Nov 22, 2008 8:23 pm**

i think i didnt understand the question correctly

anyway here is my code:

pls help

anyway here is my code:

Code: Select all

```
removed
```

Posted: **Sun Nov 23, 2008 4:10 am**

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".

Posted: **Sun Dec 07, 2008 9:29 pm**

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
```

Posted: **Mon Dec 08, 2008 6:36 pm**

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