Задача на кореневу декомпозицію з великими обмеженнями (Розбір)

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

З іншого боку, $n(n-x) = ((n-x)+x)(n-x) = x(n