C. Row GCD（数论）

题意：

输入n和m (1 <= n, m <= 2*10^5) 

随后输入n个数a[i]，

然后输入m个数b[j]，

对于每一个b[j]，求gcd(a[1] - b[j], a[2] - b[j], ......a[n - b[j])。

题解：

 1 /*
 2 因为 gcd(a, b) = gcd(a - b, b), 对于多个数来说也成立，即gcd(a, b, c, ...) = gcd(a - b, b, c, ...)
 3 因此 gcd(a[0] + b[j], a[1] + b[j], ......, a[n - 1] + b[j]) = gcd(a[0] + b[j], a[1] - a[0], ......, a[n - 1] - a[0])
 4 令GCD = gcd(a[1] - a[0], ......, a[n - 1] - a[0]), 所以结果就是 gcd(GCD, a[0] + b[j])
 5 */
 6 #include <bits/stdc++.h>
 7 
 8 using namespace std;
 9 
10 int n, m;
11 long long a[200005];
12 int main()
13 {
14     cin >> n >> m;
15     for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
16     sort(a, a + n);
17     long long GCD = 0, b_i, a_0 = a[0];
18     for (int i = 1; i < n; ++i) {
19         GCD = __gcd(GCD, a[i] - a_0);
20     }
21     for (int i = 0; i < m; ++i) {
22         scanf("%lld", &b_i);
23         b_i = __gcd(a_0 + b_i, GCD);
24         printf("%lld\n", b_i);
25     }
26     return 0;
27 }

View Code