Description：

给 $n$ 个正整数 $c_i$ ，求重排后依次取模答案的最大值。

$1\leqslant n\leqslant 10^5$

Solution：

首先将 $c$ 排序，若 $c_1$ 只出现一次答案就是 $c_1$ ，否 则答案一定小于 $c_1$ 。

发现实际有用的一定是依次递减的，也就是说问题可以变成选 $k$ 个数，降序排序然后依次模过去。

那么我们可以先把所有数降序排序，然后暴力 $dp$ ， $f[i]$ 表示数字 $i$ 是否可以达到，转移为： $$ f[i]=\bigcup_{i=1}^{n-1}\bigcup_{k}f[i+kv[i]] $$ 那么我们可以用一个 $g$ 来维护所有 $kv$ ，每次从大往小枚举判断是否可以被模出，如果这个数字已经存在，那么 $f[i]=true$ ，同时暴力在 $g$ 中标记他的所有倍数，这个是 $O(n\ln n)$ 的，如果这个数字不存在，就看 $f>>i\&g$ 是否有值，用 $bitset$ 可以优化到 $\frac {n^2}w$ 。

Code：

#include<bits/stdc++.h>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

bitset<MAXN> f,g;

bool vis[MAXN];

int main()

{

	freopen("array.in","r",stdin);

	freopen("array.out","w",stdout);

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	sort(a + 1,a + 1 + n);

	if(a[1] != a[2])

	{

		cout << a[1] << endl;

		return 0;

	}

	n = unique(a + 1,a + 1 + n) - a - 1;

	for(int i = 1,j = n;i < j;++i,--j)swap(a[i],a[j]);

	int mx = 0;

	for(int i = 1;i <= n;++i)

	{

		vis[a[i]] = true;

		mx = max(mx,a[i]);

	}

	f[0] = 1;

	for(int i = mx;i >= 1;--i)

	{

		if(vis[i])

		{

			for(int j = i;j <= mx;j += i)g[j] = 1;

			f[i] = 1;

		}

		else f[i] = ((f >> i) & g).any();

	}

	int ans;

	for(int i = a[n] - 1;i >= 0;--i)if(f[i]){ans = i;break;}

	cout << ans << endl;

	return 0;

}