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

Автор wish_me, история, 7 лет назад, По-английски

Given an array of integers. Find the total number of subarrays whose product of all elements doesn’t contain repeating prime

factor in prime decomposition of resulting number.

Input: 2 3 9

Output: 3

Explanation:

Total sub-array are:-

{2}, {3}, {9}, {2, 3}, {3, 9}, {2, 3, 9}

Subarray which violets the property are:-

{9} -> {3 * 3}, Since 3 is a repeating prime

factor in prime decomposition of 9

{3, 9} -> {3 * 3 * 3}, 3 is a repeating prime

factor in prime decomposition of 27

{2, 3, 9} -> {2 * 3 * 3 * 3}, 3 is repeating

prime factor in prime decomposition 

         of 54

Hence total subarray remains which satisfies our

condition are 3.

Input: 2, 3, 5, 15, 7, 2 Output: 12

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

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

Try all the subarrays, compute the product directly, find all its prime factors. Works on this two samples perfectly.

In other words: can you provide constraints on the length of array and array elements?

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

    arr length < 1000 and array element < 10**5 then any better approach?

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

      Let prev[i] = j denote the largest index j<i such that gcd(a[j],a[i])>1. A subarray [l,r] is valid if for all x in [l,r], prev[x]<l. Since the length of the array is small here, you can just iterate on every starting point l and try to add indices such that prex[indexes]<l. Works in O(n^2). You can also use RMQ with binary search to find r for each l, that will work in O(nlogn). prev[] array can also be built easily in O(nlog(a[i])) using prime factorisations.

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

/deleted message/

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

    Try all the subarrays subsequences, compute the product directly, find all its prime factors.

    In other words: can you provide constraints on the length of array and array elements?

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

    this is problem from live contest on hackerearth ! plz dont discuss until end of the contest