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
Did I understand right, you find gcd like, gcd(a[l], a[l + 1], a[l + 2] ... a[r])?
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
Автокомментарий: текст был обновлен пользователем RetiredPlayer (предыдущая версия, новая версия, сравнить).
Your idea is correct.
Thanks, but I can’t find maximum out of same numbers in range fast
Since 8*n is ~10^5, just apply mo's algorithm.