题目大意

选取 xx，最小化

∑i=1n⌊aix⌋+(ai mod x) \sum_{i=1}^n \left\lfloor \frac{a_i}{x} \right\rfloor + (a_i \bmod x)

分析

最小化

ans=∑i=1nai−(x−1)∑i=1n⌊aix⌋ ans = \sum_{i=1}^n a_i - (x-1)\sum_{i=1}^n \left\lfloor \frac{a_i}{x} \right\rfloor

然后我只想到了用树状数组在整除分块时维护和，后来想了想可以差分，但显然是 TLE 的。

关键在于枚举 aia_i 计算的开销是不可承受的，需要想办法统一计算。

注意到我们可以枚举 ai/xa_i / x 的值 tt，那么值为 tt 的个数便是 [tx,(t+1)x)[tx, (t+1)x) 内 aia_i 的个数。不难发现 tt 的值不会超过 A/xA / x。

const int M = 1E6;

int main() {
	int n;
	cin >> n;
	vector<int> a(n), v(M + 1);
	ll asum = 0;
	for (auto &ai : a) {
		cin >> ai;
		v[ai]++;
		asum += ai;
	}
	for (int i = 1; i <= M; i++) {
		v[i] += v[i - 1];
	}
	ll ans = 1E15;
	for (int x = 1; x <= M; x++) {
		ll sum = 0;
		for (int i = 1; i <= M / x; i++) {
			int l = i * x - 1 , r = (i + 1) * x - 1;
			r = min(r, M);
			sum += 1ll * (v[r] - v[l]) * i;
		}
		sum = asum - sum * (x - 1);
		ans = min(ans, sum);
	}
	cout << ans;

	return 0;
}

全部代码请看：Luogu/3x/P3312.cpp。