Автор: Костянтин Денисов
Розробник: Ілля Пермяков
Розбір підготовано: Костянтин Денисов
Нехай індекси утворюють небезпечну пару, якщо i<j та gcd(i,j)>1. Ціна масиву — це максимум b_i+b_j по всіх небезпечних парах (або , якщо їх немає).
Є позиції, які не входять у жодну небезпечну пару: це та всі прості p>n/2. На них жадібно вигідно ставити найбільші числа, бо вони ніяк не впливають на максимум.
Після цього візьмемо найбільше число, яке ще не поставили, і позначимо його . Будь-яка позиція, що лишилась, має хоча б одну небезпечну пару, тому значення гарантовано входить у якийсь вираз b_i+b_j. Отже відповідь не менша за . Далі розглянемо випадки mx=0,1,2,3 (бо a_i\le 3).
1. mx=0. Усі числа нулі, відповідь тривіальна.
2. mx=1. Єдина причина отримати ціну — це наявність небезпечної пари 1+1. Тому ціну можна зробити тоді і тільки тоді, коли всі одиниці стоять на попарно взаємно простих позиціях. Найпростіша конструкція: ставити одиниці на прості індекси (вони попарно взаємно прості). Якщо простих позицій (разом з , якщо потрібно) вистачає, відповідь , інакше відповідь .
3. mx=2. Можливі відповіді .
Щоб не отримати небезпечну пару 2+2=4, усі двійки мають стояти на попарно взаємно простих позиціях. Якщо це неможливо, відповідь .
Якщо двійки можна так розставити, лишається відрізнити від . Ціну можна зробити лише якщо немає небезпечної пари 2+1=3, тобто всі одиниці стоять на позиціях, взаємно простих з усіма позиціями двійок.
Конструкція для перевірки така: ставимо всі на найбільші прості позиції (позначимо ці прості через множину ), а одиниці ставимо лише в позиції, які не діляться на жоден простий із . Якщо таких позицій вистачає для всіх одиниць, відповідь , інакше відповідь .
4. mx=3. Можливі відповіді 3,4,5,6.
Щоб не отримати 3+3=6, трійки мають стояти на попарно взаємно простих позиціях. Якщо це неможливо, відповідь .
Далі, щоб мати ціну не більшу за , потрібно заборонити пари 3+2=5 та 2+2=4, тобто всі позиції з числами або разом мають бути попарно взаємно прості. Якщо це неможливо, але трійки окремо розставити можна, відповідь .
Тепер перевіримо, чи можна зробити відповідь . Для цього треба заборонити всі суми, більші за , а саме пари 2+2, 3+1, 3+2, 3+3. Умови набувають вигляду:
усі двійки стоять на попарно взаємно простих позиціях;
усі трійки стоять на попарно взаємно простих позиціях;
кожна позиція з взаємно проста з кожною позицією з (тобто двійки й трійки можна розглядати як один спільний набір на попарно взаємно простих позиціях);
кожна одиниця стоїть на позиції, взаємно простій з кожною позицією трійки (щоб не було 3+1).
Конструкція така: ставимо на найбільші прості позиції (позначимо ці прості через S_3), ставимо на інші прості позиції, а ставимо лише в позиції, які не діляться на жоден простий із S_3. Якщо позицій для одиниць вистачає, відповідь , інакше відповідь .
Реалізаційно. Потрібні прості числа до і можливість швидко рахувати позиції, що діляться на задану множину простих. Це робиться решетом Ератосфена та проходом по кратних.
Складність. Решето O(n\log\log n), усі маркування та побудова перестановки , пам'ять .