题解：AT_abc356_e [ABC356E] Max/Min

· · 题解

思路

注意到数据范围：a_i\le10^6，加之整除，因此考虑调和级数。

先对 a 排序。

我们可以在 [1,10^6] 区间内枚举 a_i 的值（注意是值）。当然也有一个小小的优化就是枚举到 a_n。

然后枚举整除的商。只需枚举到 \lfloor\dfrac{a_n}{a_i}\rfloor 即可。

一个十分显然的推论是：若 \lfloor\dfrac{a_j}{a_i}\rfloor=m，则 m\times a_i\le a_j<(m+1)\times a_i。这一部分可以使用前缀和 sum 数组来做。

然后对于每一个值可能对应多个 a_i，因此还要开一个另外的数组 tot 记录 a 序列中每个值对应几个数。

那么设枚举到了值 i，k 为我们枚举的商，那么每一次枚举答案应加上 k\times(sum_{(m+1)\times i-1}-sum_{m\times i-1})\times tot_i。即商、对应的 j 有多少个、i 在 a 序列中对应多少个数的积。

注意一个数会多次产生贡献，因此对于 i 要减掉 \dfrac{tot_i\times (tot_i+1)}{2} 。

代码

如果还不理解，看代码吧。

#include<bits/stdc++.h>
using namespace std;
long long n,ans;
long long a[200005],sum[1000005],tot[1000005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1,j=1;i<=1000000;i++){
        sum[i]=sum[i-1];//求前缀和
        while(a[j]==i){
            j++;
            sum[i]++;
            tot[i]++;//tot 代表在 a 数组中值为 i 的数量
        }
    }
    for(int i=1;i<=1000000;i++){
        for(int j=1;j<=a[n]/i;j++){
            ans+=j*(sum[(j+1)*i-1]-sum[j*i-1])*tot[i];//核心代码
        }
    }
    for(int i=1;i<=1000000;i++){
        ans-=tot[i]*(tot[i]+1)/2;
    }
    cout<<ans;
    return 0;
}

复杂度分析

调和级数的复杂度是 \operatorname{O}(n\ln n) 的。

具体可以试一试。

事实上，\dfrac{x}{1}+\dfrac{x}{2}+\cdots+\dfrac{x}{x}=x(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{x}) 趋近于 x\ln x。所以不用担心会超时。