意甲冠军：

a序列n（2*10^5）数字  问道a[i]>=a[j]如果是  a[i]%a[j]最大值是多少

思路：

感觉是一道挺乱来的题……

我们能够将ans表示为a[i]-k*a[j]  这样我们枚举k仅仅要知道比k*a[j]大可是不到(k+1)*a[j]的值就好了  考虑到a[i]仅仅要10^6大  因此能够用一个last数组记录小于等于i的数组中的数字  因此仅仅要拿出last[(k+1)*a[j]-1]就好

暴力可能会T有一些能够让程序加速的方法  输入开挂  a数字去重  从大到小枚举a[i]当ans>=a[i]时候能够break

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<map>

#include<set>

#include<vector>

#include<queue>

#include<cstdlib>

#include<ctime>

#include<cmath>

using namespace std;

typedef long long LL;

#define N 200010

#define M 1000010

int a[N], last[M];

int n, ans;

inline void scand(int &ret) {

	char c;

	ret = 0;

	while ((c = getchar()) < '0' || c > '9')

		;

	while (c >= '0' && c <= '9')

		ret = ret * 10 + (c - '0'), c = getchar();

}

int main() {

	scand(n);

	for (int i = 1; i <= n; i++) {

		scand(a[i]);

		last[a[i]] = a[i];

	}

	for (int i = 1; i < M; i++) {

		if (!last[i])

			last[i] = last[i - 1];

	}

	sort(a + 1, a + n + 1);

	n = unique(a + 1, a + n + 1) - a - 1;

	for (int i = n - 1; i >= 1; i--) {

		if (a[i] <= ans)

			break;

		for (int j = a[i] * 2; j < M && j - a[i] <= a[n]; j += a[i]) {

			ans = max(ans, last[j - 1] % a[i]);

		}

		ans = max(ans, last[M - 1] % a[i]);

	}

	printf("%d\n", ans);

	return 0;

}