传送门
B. Maximum Value
time limit per test1 second
memory limit per test256 megabytes
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·10^5).
The second line contains n space-separated integers ai (1 ≤ ai ≤ 106).
Output
Print the answer to the problem.
Examples
input
3
3 4 5
output
2
题目大意： 有一个 a 数组，里面有 n 个整数。现在要从中找到两个数字(可以是同一个) ai , aj ，使得
aimodaj 最大并且 ai≥aj 。
解题思路： 其实就是类似素数筛法一样的， 首先对 a 数组进行排序去重，因为相同的数字用一个就行了，然后
从 1−n 扫一遍，找 ai 的倍数或者不是倍数，而对 ai 取模最大的数一定介于 x∗ai 到
(x+1)∗ai 之间的一个数，而且应该是靠近 (x+1)∗ai 的，以我们就可以二分找 ai 的倍数
了，然后判断取模是不是最大就行了。
My Code ：
/** 2016 - 08 - 13 晚上 Author: ITAK Motto: 今日的我要超越昨日的我，明日的我要胜过今日的我， 以创作出更好的代码为目标，不断地超越自己。 **/ #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <set> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9+5; const int MAXN = 1e6+5; const int MOD = 1e9+7; const double eps = 1e-7; const double PI = acos(-1); using namespace std; int a[MAXN]; int main() { int n; while(~scanf("%d",&n)) { for(int i=0; i<n; i++) scanf("%d",&a[i]); sort(a, a+n); n = unique(a,a+n)-a; int ret = 0; for(int i=0; i<n; i++) { for(int j=(a[i]<<1); j<=a[n-1]; j+=a[i]) { int tmp = lower_bound(a, a+n, j) - a; if(tmp && ret<(a[tmp-1]%a[i])) ret = (a[tmp-1]%a[i]); } if(ret < (a[n-1]%a[i])) ret = (a[n-1]%a[i]); } printf("%d\n",ret); } return 0; }