给出 $n$ 个数 ，求 $\text{Min}_{x=1}^{\infty}\sum\limits_{i=1}^n(\lfloor\frac {a_i}x\rfloor+a_i\ \text{mod}\ x)$ 。

$n,a_i\le 10^6$ 。

---

题解

数学

$\text{Min}_{x=1}^{\infty}\sum\limits_{i=1}^n(\lfloor\frac {a_i}x\rfloor+a_i\ \text{mod}\ x)=\sum\limits_{i=1}^na_i-\text{Max}_{x=1}^{a}(x-1)\sum\limits_{i=1}^{n}\lfloor\frac{a_i}x\rfloor$ 

于是枚举 $x$ ，对于某个 $x$ 我们想要知道分别有多少个 $i$ ，使得 $\lfloor\frac{a_i}x\rfloor=0,1,2,...,\lfloor\frac ai\rfloor$ 。每一个都可以使用前/后缀和求出。

总的时间复杂度 $O(n+\sum\limits_{i=1}^n\frac ai)=O(n+a\log a)$ 

#include 
     
      #include 
      
       #include 
       
        using namespace std;long long sum[2000010];inline char nc(){	static char buf[100000] , *p1 , *p2;	return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;}inline int read(){	int ret = 0; char ch = nc();	while(!isdigit(ch)) ch = nc();	while(isdigit(ch)) ret = ((ret + (ret << 2)) << 1) + (ch ^ '0') , ch = nc();	return ret;}int main(){	int n = read() , m = 0 , i , j , x;	long long ans = 0 , mx = 0 , tmp;	for(i = 1 ; i <= n ; i ++ ) x = read() , sum[x] ++ , m = max(m , x) , ans += x;	for(i = m ; ~i ; i -- ) sum[i] += sum[i + 1];	for(i = 2 ; i <= m ; i ++ )	{		tmp = 0;		for(j = 0 ; j <= m ; j += i)			tmp += j / i * (sum[j] - sum[j + i]) * (i - 1);		mx = max(mx , tmp);	}	printf("%lld" , ans - mx);	return 0;}