Dora and C++
Contest: Codeforces Round 969 (Div. 2)
Difficulty rating: 1500
Tags: math, number theory

Dora has just learned the programming language C++!

However, she has completely misunderstood the meaning of C++. She considers it as two kinds of adding operations on the array $$$c$$$ with $$$n$$$ elements. Dora has two integers $$$a$$$ and $$$b$$$. In one operation, she can choose one of the following things to do.

- Choose an integer $$$i$$$ such that $$$1 \leq i \leq n$$$, and increase $$$c_i$$$ by $$$a$$$.
- Choose an integer $$$i$$$ such that $$$1 \leq i \leq n$$$, and increase $$$c_i$$$ by $$$b$$$.

Note that $$$a$$$ and $$$b$$$ are constants, and they can be the same.

Let's define a range of array $$$d$$$ as $$$\max(d_i) - \min(d_i)$$$. For instance, the range of the array $$$[1, 2, 3, 4]$$$ is $$$4 - 1 = 3$$$, the range of the array $$$[5, 2, 8, 2, 2, 1]$$$ is $$$8 - 1 = 7$$$, and the range of the array $$$[3, 3, 3]$$$ is $$$3 - 3 = 0$$$.

After any number of operations (possibly, $$$0$$$), Dora calculates the range of the new array. You need to help Dora minimize this value, but since Dora loves exploring all by herself, you only need to tell her the minimized value.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq a, b \leq 10^9$$$) — the length of the array $$$c$$$ and the constant values, respectively.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$) — the initial elements of the array $$$c$$$.

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

Output format:
For each test case, output a single integer — the minimum possible range of the array after any number of operations.

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

Note:
In the first test case, we can increase $$$c_1 = 1$$$ by $$$a = 5$$$. The array $$$c$$$ will become $$$[6, 3, 4, 4]$$$, and the range is $$$3$$$. Note that there is more than one way to reach the answer.

In the second test case, we can increase $$$c_1 = 1$$$ by $$$a = 2$$$ and then increase $$$c_1 = 3$$$ by $$$b = 3$$$. Also, we can increase $$$c_2 = 3$$$ by $$$b = 3$$$ and increase $$$c_3 = 4$$$ by $$$a = 2$$$. The array $$$c$$$ will become $$$[6, 6, 6, 6]$$$, and the range is $$$0$$$.

Example input:
10
4 5 5
1 3 4 4
4 2 3
1 3 4 6
4 7 7
1 1 2 6
3 15 9
1 9 5
3 18 12
1 4 5
7 27 36
33 13 23 12 35 24 41
10 6 9
15 5 6 9 8 2 12 15 3 8
2 1 1000000000
1 1000000000
6 336718728 709848696
552806726 474775724 15129785 371139304 178408298 13106071
6 335734893 671469786
138885253 70095920 456876775 9345665 214704906 375508929

Example output:
3
0
3
2
3
5
1
0
17
205359241

Editorial:
Read the hints.
Consider $$$a = b$$$. First, the answer is less than $$$a$$$. Otherwise, you can always increase the minimum value by $$$a$$$ so that all elements are greater than $$$\max(c_i) - a$$$. Let's go over all possible minimum values, say $$$m$$$, and we can do the operations so that all elements are in the range $$$[m, m + a - 1]$$$. Then we can calculate the range and compare it with the answer.
There are $$$n$$$ possible minimum values, so the process is too slow. Consider first letting $$$c_1$$$ be the minimum, and we do the operations to make $$$c_2 \dots c_n$$$ in the range $$$[c_1, c_1 + a - 1]$$$. Then, sort the array, and try $$$c_2, c_3, \dots c_n$$$ as the minimum in turn. Suppose $$$c_i$$$ is the current minimum, and $$$j$$$ is the largest integer such that $$$c_j < c_i$$$. If $$$j$$$ exists, then $$$c_j + a$$$ is the maximum. That's because for all $$$k < j$$$, $$$c_k + a \leq c_j + a$$$; and for all $$$k > i$$$, $$$c_k \leq c_j + a$$$. So we can do this in $$$O(n)$$$ after sorting.
In the case of $$$a \neq b$$$. We can prove that this is equivalent to $$$a = b = \gcd(a, b)$$$ according to the Bezout's Identity (Please, search it yourself on https://en.wikipedia.org/wiki/, for the character "é" cannot be displayed inside a $$$\LaTeX$$$ link): First, the changes in value of each element must be a multiple of $$$d$$$, since $$$a, b$$$ are both multiples of $$$\gcd(a, b)$$$. Second, we can always construct integers $$$x, y$$$ such that $$$ax + by = \gcd(a, b)$$$, so we can perform some operations such that we only increase / decrease an element by $$$\gcd(a, b)$$$.
Time complexity: $$$\mathcal O(n\log n + \log V)$$$.