B. Maximum Value
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/484/problem/B
Description
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 Input
3
3 4 5
Sample Output
2
HINT
题意
给你n个数(n<=1e5)，每个数(大小<=2*1e6)，要求找到最大的ai%aj（ai>aj)
题解：
类似于筛法，对于每个数，我们都筛出他的倍数
ai%aj最大，可以转化为ai*k-aj最小，记录下每个数的倍数的前面的最大的数就好了
代码
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std; int pre[]; int main()
{
int n;scanf("%d",&n);
for(int i=;i<=n;i++)
{
int x;scanf("%d",&x);
pre[x]=x;
}
for(int i=;i<=;i++)
pre[i]=max(pre[i],pre[i-]);
int ans = ;
int flag = ;
for(int i=;i<=;i++)
{
if(pre[i]==i)
for(int j=i;j<=;j+=i)
ans = max(pre[i+j-]%i,ans);
}
printf("%d\n",ans);
}