本文共 1075 字，大约阅读时间需要 3 分钟。

题目

解

n方暴力，优化了些许变nlog(n)。

代码

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;long long n,a[10000001],sl[30000001],sum[10000001],lll,sll,ans,lans,maxx;long long read(){   	long long ll = 0;	char c = getchar();	while(c > '9' || c < '0') c = getchar();	while(c <= '9' && c >= '0') {   		ll = ll * 10 + c - 48;		c = getchar();	}	return ll;}int main(){   	scanf("%lld",&n);	for(long long i = 1; i <= n; ++i){   		a[i] = read();		++sl[a[i]];		ans += a[i];	}	sort(a+1, a+1+n);	maxx = a[n];	for(int i = 1; i <= maxx * 2; ++i)   //记录值的和	    sum[i] = sum[i-1] + sl[i] * i;	for(int i = maxx; i; --i)      //记录此数后面有多少个数		sl[i] += sl[i+1];	for(long long k = maxx; k; --k){   		lans = sum[k - 1] - sum[0]; 		for(long long i = k; i <= maxx; i += k){   			lll = i / k;     //这些数都能除以lll个k			sll = sl[i] - sl[i + k]; //这些数的数量			lans += lll * sll + (sum[i + k - 1] - sum[i - 1]) - i * sll;			//TAB大小+剩余的空格		}		ans = min(ans, lans);	}	printf("%lld",ans);  }