Dora has just learned the programming language C++! However, she has completely…
- User
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≤i≤n , and increase ci by a . Choose an integer i such that 1≤i≤n , and increase ci 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(di)−min(di) . 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 Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104 ) — 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≤n≤105 , 1≤a,b≤109 ) — the length of the array c and the constant values, respectively.
The second line of each test case contains n integers c1,c2,…,cn (1≤ci≤109 ) — the initial elements of the array c .
It is guaranteed that the sum of n over all test cases does not exceed 105 .
Output For each test case, output a single integer — the minimum possible range of the array after any number of operations.
i have a approch try to make each number as close as possible to zero
- Assistant
To solve the problem, we need to minimize the range of the array after performing any number of operations. Dora can either add
aorbto any element of the arrayc. The key insights are:-
Greatest Common Divisor (GCD) Insight:
- The operations allowed (adding
aorb) mean that any element can be increased by multiples of the GCD ofaandb. Let's denoteg = gcd(a, b).
- The operations allowed (adding
-
Residue Classes:
- For each element
c_iin the array, compute its residue modulog(i.e.,r_i = c_i % g). This residue remains unchanged regardless of how many times you addaorbtoc_i.
- For each element
-
Maximum and Minimum Values for Each Residue:
- For each residue
r, determine the maximum valueL_ramong all elements in the array that share that residue. This represents the minimal value to which all elements with residuermust be increased.
- For each residue
-
Calculate the Minimum Possible Range:
- The goal is to make these
L_rvalues as close to each other as possible. The minimal possible range is determined by(max(L_r) - min(L_r)) % g, wheremax(L_r)is the largestL_randmin(L_r)is the smallestL_ramong the residues present in the array.
- The goal is to make these
By following these steps, we ensure that we align the residues in the most optimal way to minimize the range.
Final Formula:
The minimal possible range is given by: [ \text{Range} = (\text{max_L} - \text{min_L}) % g ] where:
max_Lis the maximumL_ramong all residues.min_Lis the minimumL_ramong all residues.gis the GCD ofaandb.
Implementation:
Below is the Python implementation based on the above insights:
import sys import math from collections import defaultdict def main(): import sys import math input = sys.stdin.read data = input().split() idx =0 t=int(data[idx]) idx+=1 for _ in range(t): n,a,b = map(int, data[idx:idx+3]) idx+=3 c = list(map(int, data[idx:idx+n])) idx+=n g = math.gcd(a,b) L = {} for num in c: r = num %g if r in L: if num > L[r]: L[r]=num else: L[r]=num max_L = max(L.values()) min_L = min(L.values()) S = (max_L - min_L) %g print(S) if __name__ == "__main__": main()Explanation of the Code:
-
Reading Input Efficiently:
- The input is read all at once and split into tokens for faster processing, especially since
tcan be as large as (10^4).
- The input is read all at once and split into tokens for faster processing, especially since
-
Processing Each Test Case:
- For each test case, compute the GCD
gofaandb. - For each element in
c, determine its residue modulogand store the maximumc_ifor each residue.
- For each test case, compute the GCD
-
Calculating the Minimum Range:
- Find the maximum and minimum
L_rvalues. - Compute the range using the formula ((\text{max_L} - \text{min_L}) % g).
- Find the maximum and minimum
-
Output:
- Print the minimal possible range for each test case.
Final Answer:
import sys import math from collections import defaultdict def main(): import sys import math input = sys.stdin.read data = input().split() idx =0 t=int(data[idx]) idx+=1 for _ in range(t): n,a,b = map(int, data[idx:idx+3]) idx+=3 c = list(map(int, data[idx:idx+n])) idx+=n g = math.gcd(a,b) L = {} for num in c: r = num %g if r in L: if num > L[r]: L[r]=num else: L[r]=num max_L = max(L.values()) min_L = min(L.values()) S = (max_L - min_L) %g print(S) if __name__ == "__main__": main() -