484B

Description

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$)

Tutorial

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.

Solution

#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()
{
    input();
    sort(f, f + n);
    n = unique(f, f + n) - f;
    printf("%d\n", work());
    return 0;
}