A Square Root Decomposition Problem with Large Constraints#12859

A Square Root Decomposition Problem with Large Constraints (Editorial)

Помітимо, що n\bmod (n-x) = ((n-x)+x)\bmod (n-x) = x\bmod (n-x) = x при . Отже, всі числа що строго менші за \frac{n}{2} зустрінуться серед даних чисел.

З іншого боку, n\bmod (n-x) = ((n-x)+x)\bmod (n-x) = x\bmod (n-x) \le min(x, n-x-1) \le \frac{x + (n-x-1)}{2} = \frac{n-1}{2}. Отже, всі числа з умови строго менші за \frac{n}{2}.

Таким чином, числа з умови — це цілі числа від до \lfloor \frac{n-1}{2} \rfloor, їх рівно \lfloor \frac{n+1}{2} \rfloor. Отже, достатньо просто вивести \lfloor \frac{n+1}{2} \rfloor!

Примітка: Замість викладок вище можна просто подивитись на відповіді для маленьких та помітити закономірність.