CodeForces 484B Maximum Value (数学，其实我也不知道咋分类)

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 ;

}

巴特西

CodeForces 484B Maximum Value (数学，其实我也不知道咋分类)

最新文章

热门文章