Insert and Equalize
Contest: Educational Codeforces Round 159 (Rated for Div. 2)
Difficulty rating: 1300
Tags: brute force, constructive algorithms, greedy, math, number theory

You are given an integer array $$$a_1, a_2, \dots, a_n$$$, all its elements are distinct.

First, you are asked to insert one more integer $$$a_{n+1}$$$ into this array. $$$a_{n+1}$$$ should not be equal to any of $$$a_1, a_2, \dots, a_n$$$.

Then, you will have to make all elements of the array equal. At the start, you choose a positive integer $$$x$$$ ($$$x > 0$$$). In one operation, you add $$$x$$$ to exactly one element of the array. Note that $$$x$$$ is the same for all operations.

What's the smallest number of operations it can take you to make all elements equal, after you choose $$$a_{n+1}$$$ and $$$x$$$?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$). All $$$a_i$$$ are distinct.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the smallest number of operations it can take you to make all elements equal, after you choose integers $$$a_{n+1}$$$ and $$$x$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, you can choose $$$a_{n+1} = 4$$$, the array becomes $$$[1, 2, 3, 4]$$$. Then choose $$$x = 1$$$ and apply the operation $$$3$$$ times to the first element, $$$2$$$ times to the second element, $$$1$$$ time to the third element and $$$0$$$ times to the fourth element.

In the second testcase, you can choose $$$a_{n+1} = 13, x = 4$$$.

In the third testcase, you can choose $$$a_{n+1} = 9, x = 1$$$. Then apply the operation once to $$$a_{n+1}$$$.

Example input:
3
3
1 2 3
5
1 -19 17 -3 -15
1
10

Example output:
6
27
1

Editorial:
Let's start by learning how to calculate the function without the insertion.
Since $$$x$$$ can only be positive, we will attempt to make all elements equal to the current maximum value in the array.
Pick some $$$x$$$. Now, how to check if it's possible to make every element equal to the maximum? Well, for one element, the difference between the maximum and the element should be divisible by $$$x$$$. So, for all elements, all differences should be divisible by $$$x$$$. Thus, the greatest common divisor of all differences should be divisible by $$$x$$$.
Among all values of $$$x$$$ that work, we should obviously pick the largest one. The answer is equal to $$$\sum\limits_{i=1}^n \frac{\mathit{max} - a_i}{x}$$$, so it decreases with the increase of $$$x$$$.
Thus, it only makes sense to make $$$x = \mathit{gcd}(\mathit{max} - a_1, \mathit{max} - a_2, \dots, \mathit{max} - a_n)$$$.
If you think about that from the perspective of the Euclid's algorithm of finding the gcd, you can rewrite it as $$$\mathit{gcd}(a_2 - a_1, a_3 - a_2, \dots, a_n - a_{n - 1}, \mathit{max} - a_n)$$$. Think about it on some small $$$n$$$. $$$\mathit{gcd}(a_3 - a_1, a_2 - a_1) = \mathit{gcd}((a_3 - a_1) - (a_2 - a_1), a_2 - a_1) = \mathit{gcd}(a_3 - a_2, a_2 - a_1)$$$. Basically, you can arbitrarily add or subtract the arguments of gcd from each other.
With that interpretation, it's clear that it never makes sense to make all elements equal to anything greater than the current maximum. $$$x$$$ will still be required to be divisible by all the adjacent differences, but you will be adding one more condition that can only decrease the gcd.
Let's return to the insertion. First, inserting a new element can never decrease the function. You will add one more constraint $$$a_{n+1} - a_n$$$ to the gcd. If you increase the maximum value in the array, all $$$n$$$ elements will need additional operations to become equal to it instead of the old maximum. If you don't change the maximum, $$$a_{n+1}$$$ itself will need some operations to become equal to the maximum.
Since $$$x$$$ can only decrease, let's try to not change it at all. So, we only add an element of form $$$a_i + x \cdot k$$$ for any integer $$$k$$$, if it doesn't appear in the array. Since all elements of the array are also of that form for any $$$i$$$, let's instead choose $$$a_i$$$ that is the maximum of the array. So, the form is $$$\mathit{max} + x \cdot k$$$.
If we choose a positive $$$k$$$, the maximum increases. Thus, the answer increases $$$k \cdot n$$$, since all elements will require $$$k$$$ extra operations. Obviously, it doesn't make sense to pick $$$k > 1$$$, since $$$\mathit{max} + x$$$ doesn't appear in the array already, and the number of extra operations for it is the minimum possible — just $$$n$$$.
If we choose a negative $$$k$$$, no other elements are affected. Thus, the answer only depends on the number of operations that $$$a_{n+1}$$$ will require. So, the best option is to choose the largest $$$k$$$ such that $$$\mathit{max} + x \cdot k$$$ doesn't appear in the array. Worst case, $$$k = -n$$$ if the elements are $$$[\mathit{max}, \mathit{max} - x, \mathit{max} - 2 \cdot x, \dots, \mathit{max} - (n - 1) \cdot x]$$$. The number of operations is equal to $$$-k$$$, so it's never larger than $$$n$$$. Thus, the negative $$$k$$$ is always at least as good or even better than the positive $$$k$$$.
If we change the value of $$$x$$$, we can only divide it by something. Thus, it becomes at least twice as small. Notice how it also at least doubles the current answer. The smallest possible current answer is $$$0 + 1 + 2 + \dots + (n - 1) = \frac{n \cdot (n - 1)}{2}$$$. For any $$$n > 2$$$, that is greater or equal to $$$n$$$. If we also consider that $$$a_{n+1}$$$ itself will require at least one extra operation, we can extend it to $$$n > 1$$$. So, changing $$$x$$$ is never better than not changing $$$x$$$.
Thus, we come to the final algorithm. Calculate $$$x = \mathit{gcd}(a_2 - a_1, a_3 - a_2, \dots, a_n - a_{n - 1})$$$. For $$$n = 1$$$, it's $$$0$$$, so we handle it separately — the answer can always be $$$1$$$. Then, initialize $$$k = -1$$$ and keep decreasing it by $$$1$$$ as long as $$$\mathit{max} - x \cdot k$$$ appears in the array. That can be checked with a structure like set, with a binary search over the sorted array or with two pointers. Finally, calculate the answer as $$$\sum\limits_{i=1}^n \frac{\mathit{max} - a_i}{x} - k$$$.
Overall complexity: $$$O(n \log n + \log A)$$$ per testcase.