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↵
↵
<spoiler summary="I have some idea but idk if it’s right">↵
↵
Here it is clear that each element of the array will have no more than138 unique primes, let's create a new array that will store all the i primes of that number in the same order,↵
For example if↵
↵
10 15 20↵
↵
Will become↵
↵
2 5 3 5 2 5↵
↵
then the condition will change so you need to find the maximum out of same numbers in this range↵
↵
</spoiler>↵
↵
↵
↵
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)
↵
<spoiler summary="I have some idea but idk if it’s right">↵
↵
Here it is clear that each element of the array will have no more than
For example if↵
↵
10 15 20↵
↵
Will become↵
↵
2 5 3 5 2 5↵
↵
then the condition will change so you need to find the maximum out of same numbers in this range↵
↵
</spoiler>↵
↵
