自动搬运

查看原文

来自洛谷，原作者为

	Kreado the end of this world, and the girl who crossed the moon's oceans.

搬运于2025-08-24 23:00:26，当前版本为作者最后更新于2024-07-06 21:01:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门。

思路

容易得到 $\lfloor\frac{m}{i}\rfloor$ 只有 $2\sqrt m$ 种取值，考虑对 $m$ 数论分块，对于每个区间 $\forall i,j\in[l,r]$，均有 $\lfloor\frac{m}{i}\rfloor=\lfloor\frac{m}{j}\rfloor$，令 $f(r)=\sum_{i=1}^n \sum_{j=1}^n [a_ia_j\le r]$，$b_i=\sum_{j=1}^n [a_j=i]$，那么我们有

$$f(r)=2\sum_{i=1}^{\lfloor\sqrt{r}\rfloor} b_i\left( \sum_{j=1}^n [a_j\le \lfloor\frac{r}{i}\rfloor]-\sum_{j=1}^n [a_j\le i] \right)+\sum_{i=1}^{\lfloor\sqrt{r}\rfloor} b_i^2 $$

由于传入函数 $f$ 的参数均是 $m$ 的整除点值，而 $m$ 的整除点值只有 $2\sqrt m$ 种，括号内的式子我们就可以在 $O(\sqrt m\log n)$ 的时间复杂度内求出。

那么 $f(r)$ 就能在 $O(\sqrt r)$ 的时间复杂度内求出。

最终答案就是：

$$\sum_{l,r}(f(r)-f(l-1))\times \biggl\lfloor\dfrac{m}{l}\biggl\rfloor $$

时间复杂度 $O(m^{3/4}+\sqrt m\log n)$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn=1e6+7;
const int Mod=998244353;
ll n,m;
ll a[Maxn]; 
ll sq;
ll ans;
ll sq1[Maxn],sq2[Maxn];
ll bb[Maxn];

inline ll Gt(ll x){
	if(x==0) return 0;
	if(x<=sq) return sq1[x];
	else return sq2[m/x];
}
map<ll,ll>S;
inline ll KP(ll x){
	if(S.count(x)) return S[x];
	ll res=0;
	
	ll pp=__builtin_sqrt(x);
	for(ll i=1;i<=pp;i++)
		res=(res+bb[i]*(Gt(x/i)-Gt(i)))%Mod;
	res=res*2%Mod;
	for(ll i=1;i<=pp;i++) res=(res+bb[i]*bb[i])%Mod;
	return S[x]=res;
}


int main(){
	scanf("%lld%lld",&n,&m);
	sq=sqrt(m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(a[i]<=sq) bb[a[i]]++;
	}
	sort(a+1,a+n+1);
	
	for(ll l=1,r;l<=m;l=r+1){
		r=m/(m/l);
		int res=upper_bound(a+1,a+n+1,r)-a-1;
		if(r<=sq) sq1[r]=res;
		else sq2[m/r]=res;
	}
	for(ll l=1,r;l<=m;l=r+1){
		r=m/(m/l);
		ans=(ans+(KP(r)-KP(l-1))%Mod*(m/l)%Mod)%Mod;
	}
	ans=(ans+Mod)%Mod;
	printf("%lld",ans);
	
	return 0;
}