Many Perfect Squares
Contest: VK Cup 2022 - Отборочный раунд (Engine)
Difficulty rating: 1800
Tags: brute force, math, number theory

You are given a set $$$a_1, a_2, \ldots, a_n$$$ of distinct positive integers.

We define the squareness of an integer $$$x$$$ as the number of perfect squares among the numbers $$$a_1 + x, a_2 + x, \ldots, a_n + x$$$.

Find the maximum squareness among all integers $$$x$$$ between $$$0$$$ and $$$10^{18}$$$, inclusive.

Perfect squares are integers of the form $$$t^2$$$, where $$$t$$$ is a non-negative integer. The smallest perfect squares are $$$0, 1, 4, 9, 16, \ldots$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$) — the size of the set.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ in increasing order ($$$1 \le a_1 < a_2 < \ldots < a_n \le 10^9$$$) — the set itself.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$50$$$.

Output format:
For each test case, print a single integer — the largest possible number of perfect squares among $$$a_1 + x, a_2 + x, \ldots, a_n + x$$$, for some $$$0 \le x \le 10^{18}$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, for $$$x = 0$$$ the set contains two perfect squares: $$$1$$$ and $$$4$$$. It is impossible to obtain more than two perfect squares.

In the second test case, for $$$x = 3$$$ the set looks like $$$4, 9, 16, 25, 100$$$, that is, all its elements are perfect squares.

Example input:
4
5
1 2 3 4 5
5
1 6 13 22 97
1
100
5
2 5 10 17 26

Example output:
2
5
1
2

Editorial:
The answer is obviously at least $$$1$$$.
Can we make it at least $$$2$$$? In this case, let's check all possible pairs of indices $$$i < j$$$ and try to figure out for what values of $$$x$$$ both $$$a_i + x$$$ and $$$a_j + x$$$ are perfect squares.
We can write down two equations: $$$a_i + x = p^2$$$ and $$$a_j + x = q^2$$$, for some non-negative integers $$$p < q$$$.
Let's subtract the first equation from the second one and apply the formula of difference of two squares: $$$a_j - a_i = q^2 - p^2 = (q - p)(q + p)$$$. It follows that $$$q - p$$$ is a positive integer divisor of $$$a_j - a_i$$$. It is well-known how to enumerate all divisors of $$$a_j - a_i$$$ in $$$O(\sqrt{a_j - a_i})$$$. For each such divisor $$$d$$$, we have a simple system of equations for $$$p$$$ and $$$q$$$:
$$$\begin{cases} q - p = d \\ q + p = \frac{a_j - a_i}{d} \end{cases}$$$
that we can solve:
$$$\begin{cases} p = \frac{1}{2}(\frac{a_j - a_i}{d} - d) \\ q = \frac{1}{2}(\frac{a_j - a_i}{d} + d) \\ \end{cases}$$$
and if both $$$p$$$ and $$$q$$$ turn out to be integers, that means we have found a candidate value for $$$x$$$: $$$x = p^2 - a_i = q^2 - a_j$$$.
For each candidate value of $$$x$$$, we can just calculate its squareness and find the maximum.
The complexity of this solution is $$$O(n^2 \cdot \sqrt{a_n} + n^3 \cdot f(a_n))$$$, where $$$f(a_n)$$$ is the maximum number of divisors an integer between $$$1$$$ and $$$a_n$$$ can have. The first part corresponds to finding all divisors of $$$a_j - a_i$$$ for all pairs $$$i < j$$$. The second part corresponds to checking all candidate values of $$$x$$$: there are $$$O(n^2 \cdot f(a_n))$$$ of them, and we need $$$O(n)$$$ time to calculate the squareness of each.
Bonus: The first part can be optimized by using faster factorization methods. Can you see how to optimize the second part to $$$O(n^2 \cdot f(a_n))$$$?