How to solve this problem
Разница между ru1 и ru2, 20 символ(ов) изменены
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 than 
138 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>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский RetiredPlayer 2020-08-04 00:14:16 20
ru1 Русский RetiredPlayer 2020-08-03 23:04:29 766 Первая редакция (опубликовано)