Solution:
D1. All are Same
First, if all numbers are the same, then k can be any value. So we only need to consider the situation where there are different numbers.
Because the same number can be obtained by subtracting k several times. So you can get the smallest number in the array after subtracting k several times.
So we consider the difference between each number in the array and the smallest value in the array. Then find the greatest common divisor of these differences (except 0).
D2. Half of Same
With the conclusion of D1, D2 is transformed into the following problem: Find the largest possible k so that the result of calculating the greatest common divisor according to the method of D1 for at least half of the numbers is k.
But obviously, if we enumerate half of the number by $C_{40}^{20}$, it will obviously be TLE.
We noticed that in the D1 approach, we need to use the minimum value in the array as the basis, and then calculate the greatest common divisor. For D2, the minimum value is different depending on the number selected.
So we thought of enumerating the minimum value, because n is only 40.
Now our problem becomes, given a minimum, select at least $\frac n 2 -1$ numbers to make its greatest common divisor as large as possible.
But if you use Euclid's algorithm to calculate the greatest common divisor, you need to know in advance what these numbers are, and at the same time, in order to know what these numbers are, enumeration is required.
Therefore, we directly count all the factors of each number. If a factor occurs more than $\frac n 2$, then this factor is possible to k.
So the detail approach is:
- First, we enumerate the minimum value and record it as base.
- For each number in the array (denoted as a), if the number is less than base, just ignore it. If it is greater than, then find all the factors of a-base.
- If the number of one factor exceeds $\frac n 2$, then this factor is counted as an alternative answer.
- Finally, we can find the largest one among the alternative answers.
Code:
D1
Java
C++
D2
Java
C++
