Dora and C++
题面翻译
题目描述
Dora 刚学了编程语言C++！
但是，她一点也不明白C的含义。 她认为C是两种在长度为 $n$ 的数组 $c$ 上的加法操作。Dora 有两个整数 $ a $ 与 $ b $ 。 每一次操作，她可以选择一件事情去做。
- 选择一个整数 $ i $ ，其中 $ 1 \leq i \leq n $ ，然后把 $ c_i $ 加上 $ a $ 。
- 选择一个整数 $ i $ ，其中 $ 1 \leq i \leq n $ ，然后把 $ c_i $ 加上 $ b $ 。
注意，这里 $ a $ 与 $ b $ 是常数，且他们可以相同。
让我们规定一个数组的值域 $ d $ 为 $ \max(d_i) - \min(d_i) $ 。仅举几例：数组 $ [1, 2, 3, 4] $ 的值域是 $ 4 - 1 = 3 $ ，数组 $ [5, 2, 8, 2, 2, 1] $ 的值域是 $ 8 - 1 = 7 $ ， 数组 $ [3, 3, 3] $ 的值域是 $ 3 - 3 = 0 $ 。
经过若干次操作 (可能是 $ 0 $ )， Dora 计算出了新数组的值域。 请你帮助 Dora 最小化其值，但是自从 Dora 爱上了仅凭自己探索，你只需要告诉她最小化后的值。
输入格式
每一个测试点有多组数据。第一行包括一个整数 $ t $ $( 1 \leq t \leq 10^4 )$ 代表测试数据的组数。
对于每组测试数据，第一行有三个整数 $ n $ , $ a $ $ b $ $( 1 \leq n \leq 10^5 $ , $ 1 \leq a, b \leq 10^9 )$ 表示数组 $ c $ 的长度，以及两个常数 $a$ $b$ 的值。
第二行包括 $ n $ 个整数 $ c_1, c_2, \ldots, c_n $ ( $ 1 \leq c_i \leq 10^9 $ ) 代表数组 $ c $ 的初始值。
保证对于全部的数据 $ Σn \leq 10^5 $。
输出格式
对与每组测试数据，你需要输出一个整数，表示若干次操作后数组的值域可能到达的最小值。
样例解释
第一组数据中，我们可以将 $ c_1 = 1 $ 加上 $ a = 5 $ 。 数组 $ c $ 将会变为 $ [6, 3, 4, 4] $ ，其值域为 $ 3 $ 。注意，达到正解的方案不唯一。
第二组数据中，我们可以将 $ c_1 = 1 $ 加上 $ a = 2 $ ，然后将 $ c_1 = 加上 $ by $ b = 3 $ 。当然，我们也可以将 $ c_2 = 3 $ 加上 $ b = 3 $ ，之后将 $ c_3 = 4 $ 加上 $ a = 2 $ 。数组 $ c $ 将会变为 $ [6, 6, 6, 6] $ ，其值域为 $ 0 $ .
题目描述
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.
输入格式
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 $ .
输出格式
For each test case, output a single integer — the minimum possible range of the array after any number of operations.
样例 #1
样例输入 #1
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
样例输出 #1
3
0
3
2
3
5
1
0
17
205359241
提示
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 $ .
对于一个数来说加上一个数相当于其他数减掉这个数，根据裴属定理可以求a和b的gcd，让所有的数模gcd，再排序，此事最大的和最小的就是极差，但还不是最优，排序后让a[i]+gcd和a[i+1]比较，为什么？a[i]+gcd必然是数组内最大，为什么a[i+1]是最小，如果让1~i-1所有的数都加上gcd,i还是最大，之前的也一定比a[n]大，但比i小，i+1又<i+2~n，所以i+1是最小
const int N = 2e5 + 10;
int a[N];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void solve()
{
int n, x, y;
cin >> n >> x >> y;
for (int i = 1; i <= n; i++) cin >> a[i];
int g = gcd(x, y);
for (int i = 1; i <= n; i++) a[i] %= g;
sort(a + 1, a + 1 + n);
int ans = a[n] - a[1];
for (int i = 1; i < n; i++)
{
ans = min(ans, a[i] + g - a[i + 1]);
}
cout << ans << '\n';
}
