11388 - GCD LCM

[andmej]

Is it right to say that the solution doesn't exists if and only if G is not a divisor of L?

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

[jvimal]

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]

OK, I got Accepted. Thanks. Good problem.

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

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

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

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

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

[asmaamagdi]

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

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

[asmaamagdi]

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

& I read jvimal post again and got it

Thnx all

[abid_iut]

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

Code: Select all

removed

pls help

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

[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

[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