Блог пользователя duongtnhat

Автор duongtnhat, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What do you mean by S?

Can you please specify the link of the problem?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

S is between which numbers?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, # |
Rev. 10   Проголосовать: нравится +8 Проголосовать: не нравится

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 .

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

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