【洛谷7521】[省选联考 2021 B 卷] 取模（暴力）

点此看题面

• 给定一个长度为(n)的正整数序列(a)，求((a_i+a_j)\% a_k)的最大值（(i,j,k)互不相同）。
• (nle2 imes10^5,a_ile10^8)

暴力的取模套路题

我们枚举模数(a_k)，令(p_i=a_i\% a_k)。

这样一来，(p_i+p_j)模(a_k)最多只会减一次(a_k)，而将(p_i)从小到大排序之后，要减一次(a_k)的最大答案必然是(p_{n-1}+p_n-a_k)。

不减的答案我们只要枚举(p_i)，然后二分（或利用(upper\_bound)函数）找到小于等于(a_k-1-p_i)的最大的(p_j)，用(p_i+p_j)更新一次答案。

这样做的话单次复杂度是(O(nlogn))的。

有两个显然的优化：如果模数相同不必重复做；如果模数小于等于当前答案显然不可能取得更优解，也不必再做（为此，我们要从大到小枚举模数）。

这东西看看都跑不满，因此就过了。

实际上加上这两个优化之后总复杂度据说可以证明是(O(nlognlogV))，这里就懒得去证了。

代码：(O(nlognlogV))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
using namespace std;
int n,a[N+5],p[N+5];
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	char oc,FI[FS],*FA=FI,*FB=FI;
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
int main()
{
	RI i,j;for(read(n),i=1;i<=n;++i) read(a[i]);sort(a+1,a+n+1);
	RI t=0;for(i=n;a[i]>t;--i) if(a[i]^a[i+1])//从大到小枚举模数，相同模数不重做，模数小于等于答案不可能更优不必做
	{
		for(j=1;j<=n;++j) p[j]=a[j]%a[i];sort(p+1,p+n+1),t=max(t,(p[n-1]+p[n])%a[i]);//按余数排序，计算减一次模数的最优解
		for(j=2;j^n&&p[j]+p[j+1]<a[i];++j) t=max(t,p[j]+p[upper_bound(p+j+1,p+n+1,a[i]-1-p[j])-p-1]);//枚举较小数，找到最大的相加不取模的数更新答案
	}return printf("%d
",t),0;
}