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

Help needed in number theory problem!!
Автор vasandani68, история, 8 лет назад, По-английски

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?

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

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

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

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

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

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

      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

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

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

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

        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.

        → Ответить