Codeforces 484B - Maximum Value

链接

传送门

题意

给出$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;
}