### proggerkz's blog

By proggerkz, history, 7 weeks ago,

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

• +8

 » 7 weeks ago, # |   0 Did I understand right, you find gcd like, gcd(a[l], a[l + 1], a[l + 2] ... a[r])?
•  » » 7 weeks ago, # ^ |   0 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 > 1For example if set is6 15 8 10 we need to erase 15 then gcd becomes 2
 » 7 weeks ago, # |   +8 Your idea is correct.
•  » » 7 weeks ago, # ^ |   0 Thanks, but I can’t find maximum out of same numbers in range fast
•  » » » 7 weeks ago, # ^ |   +18 Since 8*n is ~10^5, just apply mo's algorithm.