Розбір

Перш за все, відсортуємо масив позицій, в яких лежать цукерки.

Якщо $n=1$, то ми завжди можемо підібрати цю єдину цукерку, і відповідь $1$.

Якщо $n=2$, то ми можемо підібрати 2 цукерки лише тоді, коли вони не сусідні. Якщо ж цукерки сусідні, то відповідь 1. Таким чином ми вирішили блок 1.

Якщо $n=3$, то відповідь "— принаймні $2$, адже ми завжди зможемо підібрати принаймні першу та останню цукерку. Подивимось, за якої умови ми можемо підібрати всі 3 цукерки: маємо мати $(a_2-a_1)⋮x$, $(a_3-a_2)⋮x$ для деякого $x>1$. Таке $x$ знайдеться тоді й лише тоді, коли $HCD(a_2-a_1,a_3-a_2)>1$. В цьому випадку відповідь $3$, інакше - $2$. Таким чином ми вирішили блок 2.

Переведемо тепер задачу на математичну мову.

Для заданого масиву чисел потрібно знайти, для якої найбільшої кількості чисел з нього існує натуральне $x>1$, при діленні на яке всі вони дають однакові остачі.

Подивимось, як можна вирішити задачу для даного $x$. Це можна зробити за $n\log n$, якщо замінити кожне число в масиві на його остачу за модулем $x$, відсортувати, і знайти найпоширенішу остачу двома вказівниками проходом по масиву.

Помітимо, що в якості $x$ доцільно розглядати лише числа, що не перевищують максимального з $a_i$. Таким чином ми можемо вирішити блок 3, вирішивши задачу окремо для кожного $x$ з $2\le x\le 10^2$, і взявши максимум по цим значенням.

Для блоку 4 помітимо, що ми можемо перебирати лише прості значення $x$ (справді, якщо деякі числа дають однакові остачі при діленні на деяке складене число $pq$, то вони дають однакові остачі і при діленні на $p$, і при діленні на $q$). До $10^4$ є порядку $10^3$ простих чисел - асимптотика $O(10^{3}n\log n)$ заходить.

Тепер помітимо, що при $x=2$ відповідь гарантовано буде не меншою за $\lceil \frac{n}{2}\rceil$. Таким чином, в якості $x$ нам потрібно перевірити лише прості $p$, відповідь для яких може бути більшою за $\lceil \frac{n}{2}\rceil$.

Припустимо, що для деякого $p\ne 2$ є принаймні $\frac{n}{2}$ чисел, що дають при діленні на $p$ однакову остачу.

Для блоку 5 тепер можемо скористатись наступною хитрістю: за такої умови має справджуватись $a_n\ge a_1+p(\frac{n}{2}-1)\ge p(\frac{n}{2}-1)$. Таким чином, ми можемо вирішити задачу за $O(n\log n\pi (\frac{10^6}{n/2}))$, де $\pi (n)$ - кількість простих чисел, що не перевищують $n$.

Тепер перейдемо до блоку 6:

Припустимо, що для деякого $p\ne 2$ є принаймні $\frac{n}{2}$ чисел, що дають при діленні на $p$ однакову остачу. Назвемо цю групу $A$. Виберемо з наших $n$ чисел випадкову пару різних чисел. Імовірність того, що вони обидва потрапили в $A$ не менша за $\frac{1}{4}$. Таким чином, пара не повністю потрапляє в $A$ з імовірністю $\le \frac{3}{4}$. Виберемо випадковим чином $50$ пар. Імовірність того, що кожна не повністю потрапила в $A$ $\le (\frac{3}{4}{)}^{50}\le \frac{1}{10^6}$. Вірогідність дуже мала "— можна вважати, що якась пара потрапила в $A$ повністю.

Для кожної пари розглянемо всі прості дільники різниці чисел в парі. Об'єднаємо множини цих простих дільників по всім $50$ парам. З імовірністю $\ge \frac{999999}{1000000}$ серед них буде шукане просте $p$. Тому можна перебрати лише прості дільники з цієї множини. Факторизацію можна провести за $50\sqrt{max(a_i)}$. Залишилося оцінити кількість різних простих дільників.

Якщо всі $a_i$ не перевищують $A$, то кожна різниця не перевищує $A$, а отже добуток $50$ різниць не перевищує $A^{5}0$. Тепер залишилось дізнатись, скільки максимум різних простих дільників може мати число порядку $A^{50}$. Підрахунки на комп'ютері показують, що при $A=10^9$ це число буде порядку $180$. Отже, ми можемо вирішити задачу для кожного простого числа окремо, отримавши асимптотику $O(50\sqrt{max(a_i)}+180\cdot n\log n)$.