P3911 最小公倍数之和 题解

博客园同步html

原题连接c++

前置知识：web

本题的弱化版app

不难发现，原来的：svg

$\sum_{i=1}^n \sum_{j=1}^n \operatorname{lcm}(i,j)$spa

变成了：code

$\sum_{i=1}^n \sum_{j=1}^n \operatorname{lcm}(a_i , a_j)$orm

一言不合就开始推式子。xml

考虑用 $c_i$ 表示 $i$ 出现的次数，而后：htm

$\begin{aligned} & \sum_{i=1}^n \sum_{j=1}^n \operatorname{lcm}(a_i , a_j) \\ =& \sum_{i=1}^n\sum_{j=1}^n \operatorname{lcm}(i,j)\times c_i \times c_j\\ =& \sum_{i=1}^n\sum_{j=1}^n \frac{i \times j\times c_i \times c_j}{\gcd(i,j)} \\ =& \sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}[\gcd(i,j)=1]d\times i \times j \times c_{id} \times c_{jd} \\ =& \sum_{d=1}^n\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{k|\gcd(i,j)}\mu(k) \times d\times i \times j \times c_{id} \times c_{jd} \\ =& \sum_{d=1}^n\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{kd}\rfloor}\mu(k)\times d \times i \times j \times k^2 \times c_{idk} \times c_{jdk} \\ =& \sum_{T=1}^{n}T\times(\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor}i\times c_{iT})^2\sum_{k|T}\mu(k)\times k \end{aligned}$

对于后面的：

$\sum_{k|T} \mu_k \times k$

能够用 $O(n \ln n)$ 的时间完成预处理。

$n \ln n =\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$

而后，对中间那块暴力计算便可。

时间复杂度： $O(n \ln n)$.

实际得分： $100pts$.

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=5e4+1;
typedef long long ll;

inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}

inline void write(ll x) {
	if(x<0) {putchar('-');write(-x);return;}
	if(x<10) {putchar(char(x%10+'0'));return;}
	write(x/10);putchar(char(x%10+'0'));
}

int n,c[N],mu[N],prime[N];
int cnt=0; bool h[N];
ll s[N],ans=0;

inline void Euler(int n) {
	mu[1]=1; for(register int i=2;i<=n;i++) {
		if(!h[i]) mu[i]=-1,prime[++cnt]=i;
		for(register int j=1;j<=cnt && i*prime[j]<=n;j++) {
			h[i*prime[j]]=1;
			if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
			mu[i*prime[j]]-=mu[i];
		}
	} 
} 

int main() {
	n=read(); int maxi=0;
	for(register int i=1,t;i<=n;i++) {t=read(); c[t]++; maxi=max(maxi,t);}
	Euler(maxi); for(register int i=1;i<=maxi;i++)
	for(register int j=i;j<=maxi;j+=i) s[j]+=1ll*mu[i]*i; //预处理
	for(register int T=1;T<=maxi;T++) {
		ll sum=0;
		for(register int i=1;i<=maxi/T;i++) sum+=1ll*c[i*T]*i;
		ans+=T*sum*sum*s[T]; //暴力计算
	} write(ans);
	return 0;
}