最大MOD值

题意：有一个长度为n的数列a,求数列中 $a_i\%a_j(a_i\&gt;a_j)$ai​%aj​(ai​>aj​)的最大值。n<=2e5 $a_i\&lt;=1e6$ai​<=1e6

例:
n=3
a: 3 4 5
$max\left(a_i\%a_j\right)=2$max(ai​%aj​)=2

原题

思路:
对于取模运算 $b\%a=c$b%a=c ，我们可以把 $b看成b=ak+c$b看成b=ak+c 现在问题则是要使c最大。
若一个数 $x=ak+d，x\%a\&gt;b\%a$x=ak+d，x%a>b%a 则x比b更加接近 $a(k+1)$a(k+1),换句话说：则是对于模数a，
可将所有数字分在区间 $[0,a-1],[a,2a-1],[2a,3a-1]...[ka,(k+1)a-1]$[0,a−1],[a,2a−1],[2a,3a−1]...[ka,(k+1)a−1]的区间里。再对于每一个
区间，我们都采用二分找到属于该区间的最大的数x，那么这一段区间的数中模a最大的就是x。
如此对每一个数这样计算一遍，可以发现复杂度是可过的。（调和级数的复杂度）

/******************************* Author:galaxy yr LANG:C++ Created Time:2019年06月10日 星期一 22时09分07秒 *******************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+10;
int n,a[maxn],ans;
int main()
{
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
            for(int l=a[i],r=2*l-1;l<=a[n];l=r+1,r+=a[i])
                ans=max(ans,*(lower_bound(a+i,a+n+1,r+1)-1)%a[i]);
        cout<<ans<<endl;
        return 0;
}

推荐一波个人博客