题目描述
小P同学在养殖一种非常凶狠的鱼，而且与其他鱼类不同，这种鱼越大越温顺，反而小鱼最凶残。当两条鱼相遇时， 小鱼会不断撕咬大鱼，每一口都咬下与它自身等重的肉（小鱼保持体重不变），直到大鱼的体重小于这条小鱼（若 两条鱼体重相同，一条鱼会将另一条撕咬殆尽）。
现在池塘中有n条鱼，小P想知道哪一对鱼相遇后，被咬的鱼剩余体重最大。
输入格式
单组测试数据。
第一行包含一个整数n，表示鱼的数量。(1 ≤ n ≤ 2e6) 第二行有n个用空格分开的整数ai 表示第i条鱼的体重(1 ≤ ai ≤ 1e6)。
输出格式
输出一个整数代表结果。
输入输出样例
3 3 4 5
2
2 2 2
0
5 2 1 4 3 5
2
说明/提示
数据范围
对于35%的数据，1≤n≤10，1 ≤ ai ≤ 100
对于55%的数据，1≤n≤10000
对于100%的数据，1 ≤ n ≤ 2e6，1 ≤ ai ≤ 1e6
样例解释
当三条鱼的体重分别为3 4 5时，不同对鱼相遇的结果分别是{3,4}=1 {3,5}=2 {4,5}=1,所以只有第一条跟第三条鱼相 遇时，最后大鱼的体重最大，结果为2
题意
给定n个数，求一对数(i, j)，使得i>j， 且i%j最大。
题解
考虑枚举每一个数， 筛出它倍数。
对于这幅图， c%x显然大于a,b的结果，容易想到：对于每一个x的倍数， 我们取小于它的第一个数更新答案
很容易想到通过线性筛来筛倍数，但仔细想并不可以。比如12， 使用线性筛每个数只会筛一次，而12作为2，3，4，6的倍数意义是不一样的：假设12左边是10， 作为3的倍数时答案为1，4的倍数时则是2.
于是可以想到通过埃氏筛来做。
考试的时候由于边界细节只有85pts, 要注意，如果使用桶枚举可能会出现：某个数在i*x 和 (i+1)*x 之间， 而(i+1)*x 超过了枚举边间则会漏掉， 具体处理见代码。
优化
如果不是数据太水， 5e5的数据可以把 O(nlog^2n)的埃氏筛瞬间卡炸。
仔细分析后，大多数算法会被卡的情况是不一样的
数据过大：埃氏筛常数小， 复杂度稳定，但在数据过大的情况下，多一个log的致命伤就体现出来了。
数据密集：二分虽然理论上还多一个log，但是在大多数情况下完虐桶+埃氏筛。但是如果没有去重，数据密集就会被卡飞。
数据松散：刚好相反，没有一个重复的数字会让不加优化的桶卡飞（我就是
优化方式： 把上面几种加起来就好了
综合了几位大佬的写法和自己的代码，得到了一种效果显著的优化。
- 用桶储存，这样可以降低一个二分的log， 省掉一个排序，随便还能去重。
- 预处理一个last数组，储存每个数的上一个数是什么，例如
last[c] = b, last[b] = c ， 同样的last[3x] = c;
这样我们在查找3x左边的第一个数时， 直接找last[3x]即可。预处理方法见代码。
3. 反向枚举，判断一下现在枚举的这个数是否大于当前答案， 如果这个数都比答案小， 取模结果肯定更小。对答案没有贡献，直接通过。
4. 将i--改为i = last[i] , 朴素的桶在枚举时通过i--， 然后判断这个数是否存在。然而我们既然已经有last数组了，不如好好利用。直接跳到上一个存在的数显然更优。
通过这些优化以及部分细节，可以显著提升效率。 实现其实也很简单
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000006
#define rr register
int n, ans=0, las[N];
bool a[N];
//快读
int read(){
int num=0; char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0' && c<='9') num = num*10+c-'0', c=getchar();
return num;
}
int main(){
n=read();
int maxi=0;
for(rr int i=0; i<n; i++){
int l = read();
a[l] = 1;
if(a[l]) maxi = max(maxi, l);
}
rr int ls=-1;
//预处理last数组
for(rr int i=0; i<N; i++){
las[i] = ls;
if(a[i]) ls=i;
}
//i = last[i] 优化近100ms
for(rr int i=las[N-1]; i>=1; i=las[i]){
//判断是否对答案无贡献，优化100ms
if(ans >= i) continue;
//枚举倍数
for(rr int j=2; i*j<N; j++){
if(las[j*i]<=(j-1)*i) continue;
ans = max(ans, las[j*i]-(j-1)*i);
}
//处理边界问题 , 优化近200ms, 没有这一句N需要开到2倍才能AC,
ans = max(ans, maxi%i);
}
printf("%d", ans);
return 0;
}