NKOJP2468 Sum of LCM/luoguP3911 最小公倍数之和

题目：传送门

Problem

Solution

对于这种求多个\(\sum\)后面跟个\(gcd,lcm\)的式子一般都要用莫比乌斯反演。

想办法将式子化出\([n==1]\)形式

过程推导如下：

\(\sum_{i=1}^{n}\sum_{j=1}^{n}\mathrm{lcm}(A_i,A_j)\)（以下\(n\)因为与\(A_i\)同阶，所以沿用）

\(=\sum_{i=1}^{n} \sum_{j=1}^{n}\mathrm{lcm}(i,j) \times cnt_i \times cnt_j\)

\(=\sum_{i=1}^{n} \sum_{j=1}^{n} \frac{i \times j}{gcd(i,j)} \times cnt_i \times cnt_j = \sum_{k=1}^{n}\sum_{i=1}^{n} \sum_{j=1}^{n} [gcd(i,j)==k] \frac{i \times j}{k} \times cnt_{i} \times cnt_{j}\)

\(=\sum_{k=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{k}\rfloor} [gcd(i,j)==1] \frac{ik \times jk}{k} \times cnt_{ik} \times cnt_{jk}\)

\(=\sum_{k=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{k}\rfloor} \sum_{d|gcd(i,j)} μ(d) \times \frac{ik \times jk}{k} \times cnt_{ik} \times cnt_{jk}\)

\(=\sum_{k=1}^{n}\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor} μ(d) \times \frac{ikd \times jkd}{k} \times cnt_{ikd} \times cnt_{jkd}\)

\(=\sum_{k=1}^{n}\sum_{dk=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{dk}\rfloor}μ(d) \times \frac{ikd \times jkd}{k} \times cnt_{ikd} \times cnt_{jkd}\)

设\(T=dk\)，则

\(=\sum_{k=1}^{n}\sum_{T=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}μ(\frac{T}{k}) \times \frac{iT \times jT}{k} \times cnt_{iT} \times cnt_{jT}\)

\(=\sum_{k=1}^{n}\sum_{T=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}μ(\frac{T}{k}) \times i \times j \times T \times \frac{T}{k} \times cnt_{iT} \times cnt_{jT}\)

\(=\sum_{T=1}^{n}T\sum_{d|T}μ(d) \times d (\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor} cnt_{iT} \times i)^2\)

预处理出\(f[T]=\sum_{d|T}μ(d) \times d\)，最后暴力计算剩余部分即可。

时间复杂度\(O(n\sqrt n)\)

\(code:\)

#include
using namespace std;
typedef long long ll;
const int MAX_N = 50000 + 5;
int n,a[MAX_N],cnt[MAX_N];
int prime[MAX_N],isprime[MAX_N],tot,mu[MAX_N];
ll f[MAX_N],ans;
int main(){
	mu[1]=1;
	for(int i=2;i<=50000;i++){
		if(!isprime[i]){
			prime[++tot]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=tot && i*prime[j]<=50000;j++){
			isprime[i*prime[j]]=1;
			if(i%prime[j]==0) break;
			mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=50000;i++)
		for(int j=i;j<=50000;j+=i)
			f[j]+=1ll*i*mu[i];
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		cnt[a[i]]++;
	}
	for(int i=1;i<=50000;i++){
		ll tmp=0;
		for(int j=1;j<=50000/i;j++) tmp+=1ll*cnt[i*j]*j;
		ans+=1ll*i*f[i]*tmp*tmp;
	}
	printf("%lld\n",ans);
	return 0;
}