RetiredPlayer's blog

How to solve this problem
By RetiredPlayer, history, 4 years ago, In Russian

Today I created this problem, idk maybe it exists somewhere

We have array of n numbers n <= 2e4, a[i] <= 1e6 And we have q queries q <= 2e4, 1 <= l <= r <= n

Initially we have subset with element a[l:r], we need to erase minimal number of elements from this subset so that gcd(subset) > 1 gcd of subset becomes bigger than 1

I have some idea but idk if it’s right
  • Vote: I like it
  • +8
  • Vote: I do not like it

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

Did I understand right, you find gcd like, gcd(a[l], a[l + 1], a[l + 2] ... a[r])?

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

    Oh sorry, I edited the blog, i had a mistake At first we take elements a[l] ... a[r] as one set and we need to erase minimum number of element in this set to have gcd > 1

    For example if set is

    6 15 8 10

    we need to erase 15 then gcd becomes 2

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

Your idea is correct.

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

    Thanks, but I can’t find maximum out of same numbers in range fast

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

      Since 8*n is ~10^5, just apply mo's algorithm.

      → Reply