题意简介明了，需要找到一个\(T\)，最小化

\[\sum_{i=1}^n\left \lfloor \frac{a_i}{T} \right \rfloor+\sum_{i=1}^na_i\%T\]

非常显然的\(a_i\%T=a_i-\left \lfloor \frac{a_i}{T} \right \rfloor\times T\)

于是

\[\sum_{i=1}^n\left \lfloor \frac{a_i}{T} \right \rfloor+\sum_{i=1}^na_i-T\times \sum_{i=1}^n\left \lfloor \frac{a_i}{T} \right \rfloor\]

即为

\[\sum_{i=1}^na_i-(T-1)\sum_{i=1}^n\left \lfloor \frac{a_i}{T} \right \rfloor\]

最小化这个柿子只需要最大化\((T-1)\sum_{i=1}^n\left \lfloor \frac{a_i}{T} \right \rfloor\)

考虑一次枚举\(T\)，需要快速求出\(\sum_{i=1}^n\left \lfloor \frac{a_i}{T} \right \rfloor\)

注意到\(\left \lfloor \frac{a_i}{T} \right \rfloor\)只会有\(\left \lfloor \frac{\max a_i}{T} \right \rfloor\)种值，即对于\(a_i\in[0,T-1],\left \lfloor \frac{a_i}{T} \right \rfloor=0...a_i\in [kT-T,kT-1],\left \lfloor \frac{a_i}{T} \right \rfloor=k\)

我们直接暴力这\(\left \lfloor \frac{\max a_i}{T} \right \rfloor\)段区间，前缀和算一下这段区间里有多少个\(a_i\)即可

复杂度显然调和级数，视\(n\)与\(\max a_i\)同级，复杂度为\(O(n\log n)\)

代码

#include
    
     #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))const int maxn=1e6+5;inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}int n,pre[maxn],T;LL ans,tmp;inline int calc(int l,int r) {    return (r>T?pre[T]:pre[r])-(l?pre[l-1]:0);}int main() {    n=read();    for(re int x,i=1;i<=n;i++) x=read(),ans+=x,T=max(T,x),pre[x]++;    for(re int i=1;i<=T;i++) pre[i]+=pre[i-1];    for(re int i=2;i<=T;++i) {        LL now=0;        for(re int cnt=0,l=0,j=i-1;l<=T;j+=i,l+=i,++cnt)            now+=1ll*calc(l,j)*cnt;        if(1ll*now*(i-1)>tmp) tmp=1ll*now*(i-1);    }    printf("%lld\n",ans-tmp);    return 0;}