题意

给定一个序列，我们需要遍历所有不同的 $a_j$。为了最大化某个值，我们遍历所有整数 $x$（满足 $x$ 能被 $a_j$ 整除），范围从 $2a_j$ 到 $M$，其中 $M$ 是序列中最大值的两倍。对于每个这样的 $x$，我们需要找到最大的 $a_i$，使得 $a_i < x$。由于数值范围有限，我们可以用数组在 $O(1)$ 时间内完成这个查找。然后根据找到的 $a_i$ 更新答案。

思路

• 枚举序列中所有不同的元素 $a_j$。
• 对于每个 $a_j$，枚举其倍数 $x$（从 $2a_j$ 到 $M$）。
• 对于每个 $x$，快速找到小于 $x$ 的最大 $a_i$（通过预处理数组实现）。
• 利用这个 $a_i$ 更新答案。
• 时间复杂度为 $O(n \log n + M \log M)$。

算法步骤

1. 读入序列，找出最大值 $max\_val$，令 $M = 2 \times max\_val$。
2. 预处理一个数组 $best$，其中 $best[v]$ 表示小于等于 $v$ 的最大 $a_i$。
3. 对序列中的每个不同元素 $a_j$：
   • 从 $x = 2a_j$ 开始，步长为 $a_j$，直到 $x \leq M$：
     • 令 $candidate = best[x-1]$（即小于 $x$ 的最大 $a_i$）。
     • 用 $candidate$ 更新答案。
4. 输出最终答案。

复杂度分析

• 时间复杂度：$O(n \log n + M \log M)$，其中 $n$ 是序列长度，$M$ 是最大值的两倍。
• 空间复杂度：$O(M)$，用于存储预处理数组。

代码说明

• 使用一个数组 $exist$ 标记每个值是否出现，并记录最大值。
• 用另一个数组 $best$ 预处理每个位置小于等于它的最大出现值。
• 外层循环遍历所有不同的 $a_j$，内层循环枚举其倍数 $x$，通过 $best[x-1]$ 快速获取候选值并更新答案。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
const int MAXK=1e6+10;
int n,m,a[MAXN],st[MAXK+20][31],mx,lg[MAXN];
int solve(int l,int r){
	int log2r=lg[r-l+1];
	return max(st[l][log2r],st[r-(1<<log2r)+1][log2r]);
}
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=2;i<MAXK;i++)lg[i]=lg[i/2]+1;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],st[a[i]][0]=a[i],mx=max(mx,a[i]);
	int log2n=lg[mx];
	for(int j=1;j<=log2n;j++){
		for(int i=0;i<=mx-(1<<j)+1;i++){
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
    int ans=0;
    for(int i=1;i<=mx;i++){
        if(!st[i][0])continue;
        for(int j=i;j<=mx;j+=i){
            int r=solve(j,min(mx,j+i-1));
            ans=max(ans,r%i);
        }
    }
    cout<<ans;
	return 0;
}