题意：给你一个数组，你可以把数组中的数减少最多k，问数组中的所有数的GCD最大是多少？
思路：容易发现，GCD的上限是数组中最小的那个数，而因为最多可以减少k，及可以凑出来的余数最大是k，那么GCD的下限是k + 1，所以当最小的数小于等于k + 1时，答案是最小的数。如果最小的数大于k + 1,我们从大到小枚举GCD，假设当前枚举的数是x,那么如果一个数在[t * x, t * x + k]（t是一个常数）之间，那么就可以被凑出来，我们看一下最后凑出来的数是不是n个就可以了。我们可以用前缀和优化，这样查询区间操作是O(1)的。因为调和复杂度是nlogn的，所有可以过。
代码:
#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define db double
#define pii pair<int, int>
using namespace std;
const int maxn = 300010;
int a[maxn];
int sum[1000010];
int main() {
int n, k, mi = 1e9;
// freopen("Cin.txt", "r", stdin);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
mi = min(mi, a[i]);
}
if(mi <= k + 1) {
printf("%d\n", mi);
}
for (int i = 1; i <= n; i++) {
sum[a[i]]++;
}
for (int i = 1; i <= 1e6; i++)
sum[i] += sum[i - 1];
for (int i = mi; i >= k + 1; i--) {
int now = 0;
for (int j = 1; i * j <= 1e6; j++) {
now += sum[min(1000000, i * j + k)] - sum[i * j - 1];
if(now == n) {
printf("%d\n", i);
return 0;
}
}
}
}
原文：https://www.cnblogs.com/pkgunboat/p/11109569.html