題干：

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.

Examples

Input

3 3 4 5

Output

2

解題報告：

? ?拿到題，涉及取模操作，要知道可肯定和因子有關，因為a%m我可以認為是模掉了（a減去了）一個m，兩個m，三個m。。等等。這題就是利用這個原理，我們先把他離散化到數(shù)組中，然后枚舉1~1e6（相當于去重了），如果當前數(shù)字出現(xiàn)過，那就枚舉他的倍數(shù)。。。所以我們需要預處理一個bk數(shù)組，使得對于x，可以O(1)求出小于x的最大的數(shù)字。要記得處理數(shù)組的時候需要處理到2 * 1e6。因為你枚舉是剛開始就 i + i 了，細節(jié)要注意。

實際思考的思路實際是這樣：

然后考慮對于Ai來講，其能夠找到的Aj如果是Ai的因子，那么一定Ai%Aj==0.如果此時Aj是Ai的最大因子數(shù)（不包括Ai本身），那么A[ i ]%A[ j + 1 --->i-1]是會逐漸遞減的，所以那么我們每一次找到一個因子數(shù)，那么期望的最大模值肯定要在A[ i ]%A[ j + 1 ]中選取，所以我們可以考慮O(n)枚舉Ai然后sqrt(A[i])去枚舉因子數(shù)，然后過程維護一個最大值即可。總時間復雜度O(n*sqrt(n)).

我們剛剛是在枚舉因子數(shù)，所以還要話sqrt(n)的時間去算因子，反過來想，我們不妨枚舉倍數(shù)。那么我們需要枚舉1e6+1e6/2+1e6/3+1e6/4+.............1e6/1e6次，也就是logn的時間復雜度。（也就是 對于a%m，剛開始我們是枚舉a然后找對應的m，再把m改大一點點，維護最大值。現(xiàn)在變成a%m去枚舉m，然后找對應的a，再把a改小一點點，維護最大值。）

那么我們枚舉一個數(shù)之后，枚舉其倍數(shù)，對應在數(shù)組中找到比這個倍數(shù)小的最大的數(shù)，那么ans=max（ans，這個倍數(shù)小的最大的數(shù)%枚舉出來的這個數(shù)）；

實現(xiàn)方式可以二分，這樣復雜度多一個log，我們也可以先預處理出來答案然后O(1)查詢，詳情見代碼。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; ll a[MAX],ans,maxx; int bk[MAX]; const ll INF = 0x3f3f3f3f3f; int main() {memset(bk,-1,sizeof bk);int n;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i) , bk[a[i]] = a[i] , maxx = max(maxx,a[i]);sort(a+1,a+n+1);for(int i = 1; i<=2000050; i++) {if(bk[i] == -1) bk[i] = bk[i-1];}for(int i = 1; i<=1000050; i++) {if(bk[i] != i) continue;for(int j = 2*i; j<=2000050; j+=i) {if(bk[j-1] > i) ans = max(ans,1ll*bk[j-1]%i);}}printf("%lld\n",ans);return 0; }

AC代碼2：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; ll a[MAX],ans,maxx; int bk[MAX]; const ll INF = 0x3f3f3f3f3f; int main() {memset(bk,-1,sizeof bk);int n;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i) , bk[a[i]] = a[i] , maxx = max(maxx,a[i]);sort(a+1,a+n+1);for(int i = 1; i<=1000050; i++) {if(bk[i] == -1) bk[i] = bk[i-1];}for(int i = 1; i<=1000050; i++) {if(bk[i] != i) continue;for(int j = i; j<=1000050; j+=i) {if(bk[j-1] > i) ans = max(ans,1ll*bk[j-1]%i);if (bk[1000050] > i) {ans = max(ans, 1ll*bk[1000050] % i);}}}printf("%lld\n",ans);return 0; } /* 2 1000000 999999 */

TLE代碼：

for(int i = 1; i<=n; i++) {for(int j = 2*a[i]; j<=2000050; j+=a[i]) {if(bk[j-1] > a[i]) ans = max(ans,bk[j-1]%a[i]);}}

不能這么寫，，，如果是2e5個1，分分鐘給你卡成n*2.。（當然你先去重就另說了）

所以看一個題，不能直接看數(shù)據范圍算復雜度，還需要看實際實現(xiàn)代碼的姿勢的最差復雜度，或者是否有特殊樣例可以卡T，避免被卡。

總結

以上是生活随笔為你收集整理的【CodeForces - 485D】Maximum Value （枚举，用数组离散化，数学，取模运算，因子，筛法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。