484B


  Posted on 27 Nov 2014
number theory binary search

Description


You are given a sequence a consisting of integers. Find the maximum possible value of mod , where and . ()

Tutorial


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

You can do this in time with preprocess the answers for 1 to . But I would rather directly use lower_bound, the time of which is . After that, update answer by mod .

Notably, the total time complexity is . The iteration for all the and is . Because 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;
}