Codeforces 354C 暴力数论

题意：给你一个数组，你可以把数组中的数减少最多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;

			}

		}

	}

}

巴特西

Codeforces 354C 暴力数论

最新文章

热门文章

巴特西

Codeforces 354C 暴力 数论

最新文章

热门文章

Codeforces 354C 暴力数论