本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-06 22:08:50

题目考察：前缀和，二分，调和级数。
题目简述：
给你 $\{a_n\}$，求：
$$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{\max(a_i,a_j)}{\min(a_i,a_j)}\rfloor$$
数据范围：

• $1\le n\le 2\times 10^5$
• $\forall i\in[1,n],1\le a_i\le 10^6$

我们将式子变形得： $$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{\max(a_i,a_j)}{\min(a_i,a_j)}\rfloor=\sum_{i=1}^n\sum_{j=1}^n[a_j\ge a_i\land i\ne j]\times\lfloor\frac{a_j}{a_i}\rfloor$$ 我们再将 $\{a_n\}$ 升序排序变为：
$$\sum_{i=1}^n\sum_{j=1}^n[a_j\ge a_i\land i\ne j]\times\lfloor\frac{a_j}{a_i}\rfloor=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{a_j}{a_i}\rfloor$$ 那么我们考虑如何快速求 $\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^n\lfloor\frac{a_j}{a_i}\rfloor$，我们将 $\{a_n\}$ 分块，将 $\displaystyle\lfloor\frac{a_j}{a_i}\rfloor$ 相同的 $a_j$ 分在一组。设 $\displaystyle k=\lfloor\frac{a_j}{a_i}\rfloor$，则这些数一定是区间 $[ka_i,(k+1)a_i)$ 之间的数，那么我们可以用二分或者前缀和来维护个数，我用的是二分（设 $a_l\ge ka_i>a_{l-1}$，$a_{r+1}\ge(k+1)a_i>a_r$，$l,r$ 为满足上述条件的数），这组数的贡献就是 $k(r-l+1)$。
这样的做法显然可以被一半 $1$，一半不是 $1$，使复杂度退化为 $O(n^2)$，所以我们要特判相同数字。

证明时间复杂度合理：
这样运行次数最多为 $\displaystyle\sum_{i=1}^n\lfloor\frac{n-i}{i}\rfloor$，下面证明复杂度：
$$\begin{aligned}\sum_{i=1}^n\lfloor\frac{n-i}{i}\rfloor&\le\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor\&\le\sum_{i=1}^n\lfloor\frac{n}{2^{\lfloor\log_2i\rfloor}}\rfloor\&=\sum_{i=1}^{\lfloor\log_2n\rfloor}2^i\times\lfloor\frac{n}{2^i}\rfloor\&\le\sum_{i=1}^{\lfloor\log_2n\rfloor}2^i\times\frac{n}{2^i}\&=\sum_{i=1}^{\lfloor\log_2n\rfloor}n\&\le n\log_2n\end{aligned}$$ 故复杂度小于 $n\log_2n$，实际约为 $n\ln n$。

代码：

#include<bits\/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=y;++i) 
#define per(i,x,y) for(reg int i=x;i>=y;--i)
#define endl '\n'
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,a[N],ans;
signed main(){
	fst;
	cin>>n;
	rep(i,1,n) cin>>a[i];
	sort(a+1,a+n+1);
	rep(i,1,n){
		reg int l=i+1,tot=a[l]\/a[i],sum=0;
		while(l<=n){
			reg int r=lower_bound(a+l,a+n+1,a[i]*(tot+1))-a-1;
			sum+=(r-l+1)*tot;
			l=r+1;
			tot=a[l]\/a[i];
		}
		ans+=sum;
		while(a[i+1]==a[i]){
			--sum;
			ans+=sum;
			++i;
		}
	}
	cout<<ans;
	return 0;
}