题意：给你$n$个数aia_iai​,求一个$x$，使∑i=1n⌊aix⌋+ai%x\sum_{i=1}^{n}\lfloor \frac {a_i}{x}\rfloor+a_i\%x∑i=1n​⌊xai​​⌋+ai​%x最小

整除分块水题（其实严格来讲不是整除分块，只是运用了类似的思想）

考虑到如果我们把$a$从小到大排序

把⌊ai/x⌋\lfloor a_i/x \rfloor⌊ai​/x⌋相等的分成一段

考虑怎么统计这一段的答案，整除的那一块显然只需要这一段的长度乘上商

取模的那一块则可以通过

统计aia_iai​前缀和做到$O(1)$

那么显然枚举$x$,总复杂度是n+n2+n3……+1=nlognn+\frac n 2+\frac n 3……+1=nlognn+2n​+3n​……+1=nlogn

代码

#include
    
     using namespace std;inline int read(){
    	char ch=getchar();	int res=0,f=1;	while(!isdigit(ch)){
    if(ch=='-')f=-f;ch=getchar();}	while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();	return res*f;}#define ll long long#define re registerconst int N=1000005;int n,m,a[N],pos[N];ll sum[N];inline ll calc(int i){
    	re int pre=0,j;ll res=0,now;	for(j=1;j*i<=m;++j){
    		now=j*i;		res+=1ll*(pos[now]-pre)*(j-1)+(sum[pos[now]]-sum[pre]-(now-i)*(pos[now]-pre));		pre=pos[now];	}	res+=1ll*(n-pre)*(j-1)+(sum[n]-sum[pre]-(n-pre)*now);	return res;}signed main(){
    	n=read();	for(re int i=1;i<=n;i++)a[i]=read();	sort(a+1,a+n+1),m=a[n];	for(re int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];	int now=n;	for(re int i=1;i<=m;++i)pos[i]=lower_bound(a+1,a+n+1,i)-a-1;	ll ans=1e17;	for(re int i=1;i<=m;++i){
    		ans=min(ans,calc(i));	}	cout<
     
      <<'\n';}