vasandani68's blog

Help needed in number theory problem!!
By vasandani68, history, 8 years ago, In English

What can be the approach to solve this problem? I am not able to understand that when any array can have its lcm equal to its product?

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

it just means that in the subarray you choose , gcd of each two element should be 1 .

and about the approach , you can use two pointers + sieve to solve it :)

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

    Can you prove why gcd of every pair should be 1?

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

      Basic formula: lcm(a, b) = (a * b) / gcd(a, b)

      If gcd(a, b) = 1, lcm(a, b) = a * b

      Hope it's clear now :D

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

        What if n>2?

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

          I saw this problem a long time ago and gave it a shot today. Check my submission as I think there was a lot of unnecessary stuff in the Editorial.

          Solution

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

      Let's X = p[1]^a[1] * ... * p[m]^a[m], Y = p[1]^b[1] * ... * p[m]^b[m]:

      • GCD(x, y) = p[1]^min(a[1], b[1]) * ... * p[m]^min(a[m], b[m])
      • LCM(x, y) = p[1]^max(a[1], b[1]) * ... * p[m]^max(a[m], b[m])

      For array X[1], ..., X[n] we have:

      • GCD(x[1], ..., x[n]) = p[1]^min(a[1][1], ..., a[1][n]) * ... * p[m]^min(a[m][1], ..., a[m][n])
      • LCM(x[1], ..., x[n]) = p[1]^max(a[1][1], ..., a[1][n]) * ... * p[m]^max(a[m][1], ..., a[m][n])

      And X[1] * ... * X[n] = p[1]^(a[1][1] + ... + a[1][n]) * ... * p[m]^(a[m][1] + ... + a[m][n]).

      We are looking for sequence, where LCM(x[1], ..., x[n]) = X[1] * ... * X[n].

      So for every i in [1..m] max(a[i][1], ..., a[i][n]) == (a[i][1] + ... + a[i][n])

      It is true only when there is exactly one a[i][j] >= 0 and for every k != j a[i][k] == 0 (all a[i][] are non-negative).

      You can see that for any k1 != k2 GCD(X[k1], X[k2]) == 1, because min(a[i][k1], a[i][k2]) == 1 for every i in [1..m].

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

        In fact you don't need calculate gcd of any array elements. GCD(x, y) > 1, if they have at least one common prime divisor.

        So you can do 'two pointers' method (as IHaveInt mentioned earlier) and found for each i in [1..n] max length of subarray [j..i] that there is no two elements which are divided by the same prime number in that subarray.

        → Reply