B. Maximum Value
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given a sequence a consisting of n integers. Find the maximum possible value of (integer remainder of ai divided by aj), where 1 ≤ i, j ≤ n and ai ≥ aj.
Input
The first line contains integer n — the length of the sequence (1 ≤ n ≤ 2·105).
The second line contains n space-separated integers ai (1 ≤ ai ≤ 106).
Output
Print the answer to the problem.
Sample test(s)
input
3
3 4 5
output
2 题意：给一堆数，然后要求找两个数，大的数除小的数求余，求最大的余值是多少 思路：类似筛表法的思想，对于每个aj找ai。对每个aj，就for(p=aj;p<mx;p+=aj) 然后二分一下找小于a[p]且最接近a[p]的数，然后用这个数维护答案。另外一点由于这里的数只有10^6，所以可以不用二分找最靠近的数，用一个数组直接维护就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-;
const int N = ;
const int M = ;
int cas = ; int a[N];
bool vis[M];
int num[M];
int n,mxnum,ans; void run()
{
int x;
mxnum=;
memset(vis,,sizeof(vis));
memset(num,,sizeof(num));
for(int i=;i<n;i++)
{
scanf("%d",&x);
if(mxnum<x) mxnum=x;
vis[x]=;
}
for(int i=;i<=mxnum;i++)
{
if(vis[i]) num[i]=i;
else num[i]=num[i-];
}
ans=;
for(int aj=;aj<=mxnum;aj++)
{
if(!vis[aj]) continue;
if(ans<mxnum%aj) ans=mxnum%aj;
for(int p=aj*;p<=mxnum;p+=aj)
{
if(ans < num[p-]%aj)
ans = num[p-]%aj;
}
}
printf("%d\n",ans);
} int main()
{
#ifdef LOCAL
// freopen("case.txt","r",stdin);
#endif
while(scanf("%d",&n)!=EOF)
run();
return ;
}