hackercupai/hackercup huggingface dataset:
With coordinates values up to \(10^9\), we can no longer loop through each axis as in chapter 1. We can still take advantage of the fact that the \(x\) and \(y\) components of the answer can be found independently. Let's see what happens when we expand the formula for the \(x\)-component of the squared distance:

\[ \begin{aligned} \sum_{i=1}^{N} (p_x - A_i)^2 &= \sum_{i=1}^{N} [\,p_x^2 - 2 p_x A_i + A_i^2] \\ &= \sum_{i=1}^{N} p_x^2 - \sum_{i=1}^{N} 2 p_x A_i + \sum_{i=1}^{N} A_i^2 \\ &= N p_x^2 - 2 p_x \sum_{i=1}^{N} A_i + \sum_{i=1}^{N} A_i^2 \end{aligned} \]

The sums in the middle and last terms do not actually depend on the query, so they can both be precomputed as constants. The rest is just arithmetic, done in \(\mathcal{O}(1)\) per query.

Special care must be taken with the modular arithmetic of these computations. Overflows of 64-bit integers can happen easily if more than two terms are multiplied without modding. Also since subtraction is involved, the remainder operator \(\%\) in many languages may yield negative results where the number theoretic modulo would be positive. One possible way to implement modular subtraction using the \(\%\) operator is \((a - b) \text{ mod } M = ((a\;\%\;M) - (b\;\%\;M) + M) \;\%\;M\).

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=bUa3fyd2Fus)