当前位置：网站首页>Codeforces Round ＃276 (Div. 1) B. Maximum Value

Codeforces Round ＃276 (Div. 1) B. Maximum Value

2022-08-10 12:05:00 【Snow_raw】

Codeforces Round #276 (Div. 1) B. Maximum Value

题意： 给定一个长为 $n$ 的序列 ${ a_i\}$ ，求序列中最大的 $a [i]$ $m o d$ $a [j]$ 其中 $a_i>a_j$

思路： 考虑到 $a_i$ 的取值最大为 $10^6$ ，我们可以暴力枚举 $a_i$ 的倍数，枚举值不超过 $2*10^6$ 即可，看似 $O(n^2)$ 的复杂度，实则符合调和级数的性质，即 $N$ $*$ $1$ $+$ $N$ $*$ $\dfrac{1}{2}$ $+$ $N$ $*$ $\dfrac{1}{3}$ $...$ $=$ $Nl o g N$ ，然后再通过前缀和操作， $O (n)$ 预处理出来每个数离当前数倍数最近的数，从而不断更新最大的模数。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2E6+10;
bool vis[N];
int pre[N];
int n;
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
    
        int x;
        cin>>x;
        vis[x]=true;
    }
    for(int i=1;i<N;i++){
    
        if(vis[i])pre[i]=i;
        else pre[i]=pre[i-1];
    }
    int ans=0;
    for(int i=2;i<N;i++){
    //调和级数
        if(vis[i]){
    
            for(int j=2*i;j<N;j+=i){
    
                ans=max(ans,pre[j-1]%i);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

原网站

版权声明
本文为[Snow_raw]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_53504307/article/details/126247681

当前位置：网站首页>Codeforces Round ＃276 (Div. 1) B. Maximum Value

Codeforces Round ＃276 (Div. 1) B. Maximum Value

Codeforces Round #276 (Div. 1) B. Maximum Value

边栏推荐

猜你喜欢

随机推荐