链接
传送门
题意
给出\(n (1 \leq n \leq 2 \cdot 10^5)\)个数，其中\(1 \leq a_i \leq 10^6\)，求满足\(1 \leq i,j \leq n,a_i \geq a_j\)最大的\(a_i \bmod a_j\)。
思路
很久前的一道题，一直没写题解，今天回想起来，记录一下。 对于每个数\(x\)，记录满足\(x > a_i\)最大的\(b_x=a_i\)，然后可以枚举每个\(a_j\)的倍数来找到\(b_{k \cdot a_i} \bmod a_j\)的最大值。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200010;
const int maxm = 2000010;
int a[maxn], b[maxm];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
sort(a, a + n);
n = int(unique(a, a + n) - a);
a[n] = maxm;
int p = a[0] + 1;
for (int i = 1; i <= n; ++i) {
while (p <= a[i]) {
b[p++] = a[i - 1];
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = a[i] << 1; j < maxm; j += a[i]) {
ans = max(ans, b[j] - j + a[i]);
}
}
printf("%d\n", ans);
return 0;
}
|