先按照 $V_i$ 从大到小排序。

于是 $V_1$ 最大，也就代表他是第一名。

所以当第一名跑完用时 $t=\frac{K\times C}{v_1}$，此时其他人跑的路程为 $V_i\times t$。

但是我们发现，$t$ 的值不一定为整数，但是 $t$ 的分母为 $V_1$ 为整数，所以我们令 $t=t\times V_1=K\times C$，此时 $t$ 为整数。

下面令 $C=C\times V_1$，此时分子和分母均含有 $V_1$，更好计算。

所以答案

$$ans=\sum_{i=1}^{n}\sum_{j=i+1}^{n} \lfloor \frac{v_i\times t-v_j\times t}{C} \rfloor $$

令 $s_i=v_i\times t$，则答案

$$ans=\sum_{i=1}^{n}\sum_{j=i+1}^{n} \lfloor \frac{s_i-s_j}{C} \rfloor $$

将里面的式子变形，得

$$\lfloor \frac{s_i-s_j}{C} \rfloor \\=\frac{(s_i-s_j)-(s_i-s_j)\bmod C}{C} \\ =\frac{(s_i-s_j)-(s_i\bmod C-s_j\bmod C+C)\bmod C}{C}$$

于是答案

$$ans=\sum_{i=1}^{n}\sum_{j=i+1}^{n}\frac{(s_i-s_j)-(s_i\bmod C-s_j\bmod C+C)\bmod C}{C}\\ =\sum_{i=1}^{n} \frac{(s_i-s_{i+1})+(s_i-s_{i+2})+\cdots+(s_i-s_n)-((s_i\bmod C-s_{i+1}\bmod C+C)\bmod C+\cdots+(s_i\bmod C-s_n\bmod C+C)\bmod C)}{C} \\=\sum_{i=1}^{n}\frac{(n-i)s_i-\sum_{j=i+1}^n s_j-((s_i\bmod C-s_{i+1}\bmod C+C)\bmod C+\cdots+(s_i\bmod C-s_n\bmod C+C)\bmod C)}{C}$$

令 $ssum_i=s_1+\cdots+s_i,msum_i=(s_1\bmod C)+\cdots + (s_i \bmod C)$ 则 $ans=\sum_{i=1}^{n}\frac{(n-i)s_i-(ssum_n+ssum_i)-((s_i\bmod C-s_{i+1}\bmod C+C)\bmod C+\cdots+(s_i\bmod C-s_n\bmod C+C)\bmod C)}{C}$

现在就是求 $((s_i\bmod C-s_{i+1}\bmod C+C)\bmod C+\cdots+(s_i\bmod C-s_n\bmod C+C)\bmod C)$ 的值。

对于 $(s_i\bmod C-s_j\bmod C+C)$ 来说： 当 $s_i\bmod C\ge S_j\bmod C$ 时，此时原式为 $s_i\bmod C-s_j\bmod C$ 否则，原式为 $s_i\bmod C-s_j\bmod C+C$

所以：

$$((s_i\bmod C-s_{i+1}\bmod C+C)\bmod C+\cdots+(s_i\bmod C-s_n\bmod C+C)\bmod C)\\=(n-i)(s_i\bmod C)-\sum_{j=i+1}^n (s_j \bmod C) + (s_i \bmod C < s_j \bmod C 的数量)\times C\\ =(n-i)(s_i\bmod C)-\sum_{j=i+1}^n (s_j \bmod C) + (s_j \bmod C > s_i \bmod C 的数量)\times C \\=(n-i)(s_i\bmod C)-(msum_n-msum_i) + ((n-i)-(s_j \bmod C \le s_i \bmod C 的数量)\times C$$

我们可以用一个树状数组去存储 $s_? \bmod C$ 的值，从 $i=n$ 到 $1$ 去求，每次先查询 $i=0$ 到 $s_i\bmod C$ 的和，再在余数的位置加上 $1$。

于是答案变为了

$$ans=\sum_{i=1}^{n}\frac{(n-i)s_i-(ssum_n+ssum_i)-((n-i)(s_i\bmod C)-(msum_n-msum_i)+((n-i)-getsum(s_i\bmod C))\times C)}{C} $$

实际运行中需要 $i$ 从 $n$ 到 $1$，每次计算完答案后记得 $insert(s_i\bmod C,1)$

记得预处理 $s_i\bmod C$ 和离散化。

时间复杂度 $O(n\log n)$，可以通过。 代码（赛后）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
ll lowbit(int x){
	return x&(-x);
}
int zy=100000;
int tr[100005];
void insert(int c,int m){
	for(;c<=zy;c+=lowbit(c)) tr[c]+=m;
}
int getsum(int k){
	int sum=0;
	for(;k;k-=lowbit(k)) sum+=tr[k];
	return sum;
}
int getsum(int l,int r){
	if(l>r) return 0;
	else return getsum(r)-getsum(l-1);
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,K,C;
	cin>>n>>K>>C;
	ll v[n+5],s[n+5],msum[n+5],ssum[n+5],m[n+5];
	for(int i=1; i<=n; i++) cin>>v[i];
	sort(v+1,v+n+1,[](ll a,ll b){
		return a>b; 
	});
	int cnt=0,t=K*C;
	C=C*v[1];
	msum[0]=ssum[0]=0;
	vector<int> vv;
	for(int i=1; i<=n; i++){
		s[i]=v[i]*t;
		m[i]=s[i]%C;
		vv.push_back(m[i]);
		msum[i]=msum[i-1]+m[i];
		ssum[i]=ssum[i-1]+s[i];
	}
	sort(vv.begin(),vv.end());
	vv.erase(unique(vv.begin(),vv.end()),vv.end());
	for(int i=n; i>=1; i--){
		cnt+=((n-i)*s[i]-(ssum[n]-ssum[i])-((n-i)*m[i]-(msum[n]-msum[i])+((n-i)-getsum(lower_bound(vv.begin(),vv.end(),m[i])-vv.begin()+1))*C))/C;
		insert(lower_bound(vv.begin(),vv.end(),m[i])-vv.begin()+1,1);
	}
	cout<<cnt;
	return 0;
}

代码 $2$（赛时，写题解的时候不知道怎么思考的了 qwq），式子差不多，只是模数对象不同且无需离散化。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
ll lowbit(int x){
	return x&(-x);
}
int zy=1000000;
int tr[1000005];
void insert(int c,int m){
	for(;c<=zy;c+=lowbit(c)) tr[c]+=m;
}
int getsum(int k){
	int sum=0;
	for(;k;k-=lowbit(k)) sum+=tr[k];
	return sum;
}
int getsum(int l,int r){
	if(l>r) return 0;
	else return getsum(r)-getsum(l-1);
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,k,c;
	cin>>n>>k>>c;
	ll v[n+5],s[n+5],q[n+5],s2[n+5];
	for(int i=1; i<=n; i++) cin>>v[i];
	sort(v+1,v+n+1,[](ll a,ll b){
		return a>b; 
	});
	int cnt=0,t=v[1];
	s[0]=0;s2[0]=0;
	for(int i=1; i<=n; i++) v[i]*=k,q[i]=v[i]%t,s[i]=s[i-1]+v[i],s2[i]=s2[i-1]+q[i];
	for(int i=n; i>=1; i--){
		cnt+=(((n-i)*v[i]-s[n]+s[i])-((n-i)*q[i]-s2[n]+s2[i])-(((n-i)-getsum(q[i]+1))*t))/t; 
		insert(q[i]+1,1);
	}
	cout<<cnt;
	return 0;
}