duongtnhat's blog

A problem about LCM and GCD
By duongtnhat, 10 years ago, In English

Have a set A. First there are n (n<=40000) number in A. If u and v are in A, LCM(u, v) and GCD(u, v) are in A, too. Give A and a number S, is S in A? Sorry, my English isn't good.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean by S?

Can you please specify the link of the problem?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    http://codeforces.net/gym/100442 Problem E here. Multitest, number of tests is given in the first line. Every test is n + array of length n (elements  ≤ 1018) + the number you need to check. Output YES or NO.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

S is between which numbers?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that this problem is:

Given set of intergers. You need to check if given number is equal to LCM of two elements of set.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    No, it is not. Imagine n = 3, and initial numbers:
    2 3 5
    then A = {2, 3, 5, 1, 2 * 3, 3 * 5, 2 * 5, 2 * 3 * 5}.

    edit: added 2 * 5, thx misof.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You missed 2*5 in your example.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My intuition says that the answer is yes iff, for each prime p, there is some element x such that p divides x and p divides S an equal number of times.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    That's not true for S={6,36} and x=12

    → Reply
»
10 years ago, # |
← Rev. 10   Vote: I like it +8 Vote: I do not like it

Let’s call the set of n numbers given in the input data A0. In mathematical terms, A is the closure of A0 under LCM and GCD.

Now we’ll see that every number in A can be represented as the LCM of some GCDs of some numbers from A0. So we can take the closure of A0 under GCD first and then take the closure of that under LCM to get A. The proof is by induction:

  • Clearly, every element of A0 is already in this form: .
  • Now, if we have two elements of A that are in this form, say, and with , we can
    • either take the LCM of them: then is in the form we want,
    • or take the GCD of them: then is also in the form we want.

If there is a reasonably small limit on the values of the input numbers, , we can actually compute the closure of A0 under GCD:

gcd_closure = {}
for i from 1 to max(A0):
    multiples = {}
    for j from i to max(A0) step i:
        if j in A0:
            multiples.add(j)
    if gcd(multiples) == i:
        gcd_closure.add(i)

This takes time because and because gcd(x, y) takes time .

Now we just need to determine whether S is the LCM of some subset of gcd_closure. We can do it similarly:

divisors = {}
for d in gcd_closure:
    if S mod d == 0:
        divisors.add(d)
answer = (lcm(divisors) == S)

This takes time because and lcm(x, y) takes the same time as gcd(x, y) plus .

So the whole solution takes time and memory .

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

As we're all throwing random thoughts, my intuition says if the prime factorization of S is product pi ^ ai, and Bi = gcd({ x in A0 : pi^ai divides x}), S is in A iff lcm Bi = S.

I can't formally prove it, but it feels right... Edit: winger proved it in a reply below.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That sounds right, since for each power of a prime dividing S, you are sure to have it in your final number if there is a number with that power as a factor, and you will remove any extraneous primes with the gcd, if it is possible to.

    One corner case however is when gcd(A)!=1 and S=1, but that's easily fixed.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fails on A0 = {20, 25, 250},  S = 100. Clearly , but using this (hypothetical) solution, from S = 22 × 52 we get and , and so S is rejected.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      4 doesn't divide 250, so B2 is gcd(20)=20.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Here's the proof:

    First, let's prove that Bi is the smallest (in terms of divisibility) element of A that is divisible by piai:

    Suppose that there is another element of A Bi', that is divisible by piai but not by Bi. Let's also choose Bi' with the smallest formula. The fact that Bi' is not divisible by Bi means that there is prime number power pk that divides Bi but not Bi'. Obviously, p ≠ pi and Bi' is not equal to one of the generators.

    • If Bi' = GCD(L, R), both L and R are divisible by piai and at least one of them is not divisible by pk.
    • If Bi' = LCM(L, R), both L and R are not divisible by pk and at least one of them is divisible by piai.

    In both cases, we found a number that is divisible by piai but not by Bi and with smaller formula than Bi'. Contradiction.

    Now, it is easy to show that S is in A iff it is divisible by all Bi, which is equivalent to S = LCM(Bi) (because LCM(Bi) is obviously divisible by S).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Nice! I guess this settles the problem, then. :)

      → Reply