Skip to content



You are given a sequence a consisting of n integers. Find the maximum possible value of a_i mod a_j, where 1 \leq i, j \leq n and a_i \geq a_j. (n \leq 2 \times 10^5)


Sort the sequence first. Let us iterate over all different a_j. Since we need to maximize, then iterate all integer x (such x divisible by a_j) in range from 2 \times a_j to M, where M is the sum of the max value in the sequence and a_j. For each such x we need to find maximum a_i, such a_i < x.

You can do this in time O(1) with preprocess the answers for 1 to 10^6. But I would rather directly use lower_bound, the time of which is O(logN). After that, update answer by a_i mod a_j.

Notably, the total time complexity is O(NlogN + MlogMlogN). The iteration for all the a_j and x is O(MlogM). Because \sum\limits_{i=1}^{M} \frac{M}{i} \approx O(MlogM) which can be deducted from Euler-Mascheroni constant.


#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;

#define MAX_N 200005
#define D(x)

int n;
int f[MAX_N];

void input()
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &f[i]);

int work()
    int ret = 0;
    for (int i = 0; i < n; i++)
        for (int j = 2; j * f[i] <= f[n - 1] + f[i]; j++)
            int temp = *(lower_bound(f, f + n, f[i] * j) - 1);
            ret = max(ret, temp % f[i]);
    return ret;

int main()
    sort(f, f + n);
    n = unique(f, f + n) - f;
    printf("%d\n", work());
    return 0;