Three Days Grace
Contest: Codeforces Round 804 (Div. 2)
Difficulty rating: 2600
Tags: data structures, dp, greedy, math, number theory, two pointers

Ibti was thinking about a good title for this problem that would fit the round theme (numerus ternarium). He immediately thought about the third derivative, but that was pretty lame so he decided to include the best band in the world — Three Days Grace.

You are given a multiset $$$A$$$ with initial size $$$n$$$, whose elements are integers between $$$1$$$ and $$$m$$$. In one operation, do the following:

- select a value $$$x$$$ from the multiset $$$A$$$, then
- select two integers $$$p$$$ and $$$q$$$ such that $$$p, q > 1$$$ and $$$p \cdot q = x$$$. Insert $$$p$$$ and $$$q$$$ to $$$A$$$, delete $$$x$$$ from $$$A$$$.

Note that the size of the multiset $$$A$$$ increases by $$$1$$$ after each operation.

We define the balance of the multiset $$$A$$$ as $$$\max(a_i) - \min(a_i)$$$. Find the minimum possible balance after performing any number (possible zero) of operations.

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

The second line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 5 \cdot 10^6$$$) — the initial size of the multiset, and the maximum value of an element.

The third line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the elements in the initial multiset.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$ and the sum of $$$m$$$ across all test cases does not exceed $$$5 \cdot 10^6$$$.

Output format:
For each test case, print a single integer — the minimum possible balance.

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

Note:
In the first test case, we can apply the operation on each of the $$$4$$$s with $$$(p,q) = (2,2)$$$ and make the multiset $$$\{2,2,2,2,2,2,2\}$$$ with balance $$$\max(\{2,2,2,2,2,2,2\}) - \min(\{2,2,2,2,2,2,2\}) = 0$$$. It is obvious we cannot make this balance less than $$$0$$$.

In the second test case, we can apply an operation on $$$12$$$ with $$$(p,q) = (3,4)$$$. After this our multiset will be $$$\{3,4,2,3\}$$$. We can make one more operation on $$$4$$$ with $$$(p,q) = (2,2)$$$, making the multiset $$$\{3,2,2,2,3\}$$$ with balance equal to $$$1$$$.

In the third test case, we can apply an operation on $$$35$$$ with $$$(p,q) = (5,7)$$$. The final multiset is $$$\{6,5,7\}$$$ and has a balance equal to $$$7-5 = 2$$$.

In the forth test case, we cannot apply any operation, so the balance is $$$5 - 1 = 4$$$.

Example input:
4
5 10
2 4 2 4 2
3 50
12 2 3
2 40
6 35
2 5
1 5

Example output:
0
1
2
4

Editorial:
We can see that in the final multiset, each number $$$A_i$$$ from the initial multiset will be assigned to a subset of values $$$x_1, x_2,....,x_k$$$ such that their product is $$$A_i$$$. Every such multiset can be created. Also let $$$vmax$$$ be the maximum value in the initial multiset.
Now , if we did any operation, the minimum value already becomes at most $$$\sqrt{vmax}$$$, and if we did no operations, then it's easy to see that we can just update the answer by the initial balance. Now, consider iterating through the minimum value. To get the best maximum value that has this minimum we fixed, one can use dynamic programming $$$dp[i][j] = $$$the best possible maximum if we had number $$$i$$$ and the minimum value in the product is $$$j$$$, $$$j$$$ is a divisor of $$$i$$$. This dp can be calculated in $$$O(vmax \cdot log^2(vmax))$$$ for all values. Thus , the final time complexity is $$$O(N \cdot \sqrt{vmax}$$$). The second part can be reduced to $$$O(vmax \cdot log^2(vmax))$$$ using some kind of sweepline – each time our minimum increases, we update only the values we care abot, there will be atmost $$$vmax \cdot log(vmax)$$$ updates, but even with this optimization, this solution is not enough to pass.
Here is a way more elegant solution ( thanks to [user:cadmiumky] ). To further optimize it one can notice that we can calculate both the $$$dp$$$ and the best balance at the same time. Let's say we want all elements in the multiset to be at least $$$L$$$ and for this we keep $$$dp_i =$$$ minimum maximum value such that $$$i$$$ is decomposed into values $$$\ge L$$$. The observation that helps us update this really fast is that all values that can be changed are always multiples of $$$L$$$ , else we could just relay on what was calculated at step $$$L+1$$$. So we can just update the dp values for multiples of $$$L$$$ by $$$dp_i = min(dp_{\frac{i}{L}},dp_i)$$$. The updates are done in increasing order of $$$i$$$ so we can take into account having multiple factors of $$$L$$$. After this we need to recalculate the balance. For this we can just simply keep a pointer that tells us which was the previous minimum maximum value and decrease it while we can. Since it can only decrese $$$vmax$$$ times, and all the updates take $$$O(vmax \cdot log(vmax))$$$ time in total ( refer to harmonic series ), our time complexity will be $$$O(vmax \cdot log(vmax))$$$ with a quite low constant.