给出 $n$ 个数 ，求 $ ext{Min}_{x=1}^{infty}sumlimits_{i=1}^n(lfloorfrac {a_i}x floor+a_i ext{mod} x)$ 。
$n,a_ile 10^6$ 。
题解
数学
$ ext{Min}_{x=1}^{infty}sumlimits_{i=1}^n(lfloorfrac {a_i}x floor+a_i ext{mod} x)=sumlimits_{i=1}^na_i- ext{Max}_{x=1}^{a}(x-1)sumlimits_{i=1}^{n}lfloorfrac{a_i}x floor$
于是枚举 $x$ ，对于某个 $x$ 我们想要知道分别有多少个 $i$ ，使得 $lfloorfrac{a_i}x floor=0,1,2,...,lfloorfrac ai floor$ 。每一个都可以使用前/后缀和求出。
总的时间复杂度 $O(n+sumlimits_{i=1}^nfrac ai)=O(n+alog a)$
#include <cstdio>
#include <cctype>
#include <algorithm>
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;
}