Codesforces 485D Maximum Value

D. Maximum Value

You are given a sequence a consisting of n integers. Find the maximum possible value of (integer remainder of ai divided byaj), 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

给出 n 个数 a[0] ~ a[n-1] ，要你找出 a[i] % a[j] 最大.

处理一个数组x[i]表示 1~i 离i最近的数是什么。就可以过了。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = (1e9+);

const int N = ;

bool num[N];

int x[N] , a;

int main()

{

    int n ;

    cin >> n ;

    for( int i =  ; i < n ; ++i ) {

        cin >> a;

        num[a] =  ;

    }

    for( int i =  ; i <= 2e6 ; ++i ){

        if( num[i] )x[i] = i ;

        else x[i] = x[i-] ;

    }

    int res =   ;

    for( int i =  ; i <= 1e6 ; ++i ) if( num[i] ){

        for( int j =  * i ; j <= 2e6 ; j += i ) {

            res = max( res , ( x[j-] ) % i );

        }

    }

    cout << res << endl;

}

巴特西

Codesforces 485D Maximum Value

最新文章

热门文章