2026“钉耙编程”中国大学生算法设计春季联赛（8）1006思路分享（莫比乌斯反演）

题意概述

给定长分别为 \(n,m\) 的数组 \(a,b\)，求：

\[\sum_{i=1}^{n}{\sum_{j=1}^{m}{\frac{lcm(a_i,b_j)}{gcd{(a_i,b_j)}}}} \]

模 \(10^9+7\)。

思路

记值域为 \(V\)，\(cnt1[x]\) 为 \(a\) 中 \(x\) 出现次数，\(cnt2[y]\) 为 \(b\) 中 \(y\) 出现的次数。

原式为：

\[\sum_{x=1}^{V}{\sum_{y=1}^{V}{cnt1[x] \cdot cnt2[y] \cdot \frac{lcm(x,y)}{gcd(x,y)}}} \]

将 \(lcm\) 化掉，得：

\[\sum_{x=1}^{V}{\sum_{y=1}^{V}{cnt1[x] \cdot cnt2[y] \cdot \frac{x}{gcd(x,y)} \cdot \frac{y}{gcd(x,y)}}} \]

枚举 \(d=gcd(x,y)\)，得：

\[\sum_{d}{\sum_{x}^{V/d}{\sum_{y}^{V/d}{cnt1[xd] \cdot cnt2[yd] \cdot x y [gcd(x,y)=1]}}} \]

根据莫比乌斯函数的性质，把 \(gcd(x,y)\) 化掉，得：

\[\sum_{d}{\sum_{x}^{V/d}{\sum_{y}^{V/d}{cnt1[xd] \cdot cnt2[yd] \cdot x y \sum_{k\mid gcd(x,y)}{\mu(k)}}}} \]

交换求和，换元化简，得：

\[\sum_{d}{\sum_{k}{\mu(k)\cdot k^2 \left(\sum_{x}^{V/d/k}{cnt1[kdx]\cdot x}\right) \left(\sum_{y}^{V/d/k}{cnt2[kdy]\cdot y}\right) }} \]

令 \(T=kd\)，得：

\[\sum_{T}^{V}{\left( \sum_{k\mid T}{\mu(k)\cdot k^2}\right) \left(\sum_{x}^{V/T}{cnt1[Tx]\cdot x}\right) \left(\sum_{y}^{V/T}{cnt2[Ty]\cdot y}\right)} \]

令从左到右括号内式子分别为 \(f(x),g(x),h(x)\)。

原式就变成：

\[\sum_{T}^{V}{f(T)\cdot g(T) \cdot h(T)} \]

\(g(x)\) 和 \(h(x)\) 可以在调和级数时间内暴力求出。

对于 \(f(x)\)，注意到 \(\mu(k)\cdot k^2\) 是积性函数，同时 \(f(x)\) 是狄利克雷卷积的形式，所以 \(f(x)\) 是积性函数，可以用欧拉筛在线性时间内求出。

时间复杂度 \(\mathcal{O}(T\cdot V\log V)\)。

代码

//author:kzssCCC

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

const int V = 1e6;
const int MOD = 1e9+7;

ll A[V+1],B[V+1],C[V+1];

void init(){
	vector<bool> f(V+1,true);
	f[0] = f[1] = false;
	vector<int> prime;
	A[1] = 1;

	for (int i=2;i<=V;i++){
		if (f[i]){
			A[i] = (1-(ll)i*i%MOD+MOD)%MOD;
			prime.push_back(i);
		}

		for (auto& v:prime){
			if ((ll)v*i>V) break;
			f[v*i] = false;

			if (i%v==0){
				A[v*i] = A[i];
				break;
			}

			A[v*i] = A[v]*A[i]%MOD;
		}
	}
}

void solve(){
	int n,m;
	cin >> n >> m;

	vector<int> a(n+1),cnt1(V+1);
	for (int i=1;i<=n;i++){
		cin >> a[i];
		cnt1[a[i]]++;
	}

	vector<int> b(m+1),cnt2(V+1);
	for (int i=1;i<=m;i++){
		cin >> b[i];
		cnt2[b[i]]++;
	}

	for (int t=1;t<=V;t++){
		B[t] = 0;
		for (int x=1;x<=V/t;x++){
			B[t] = (B[t]+x*cnt1[x*t]%MOD)%MOD;
		}

		C[t] = 0;
		for (int y=1;y<=V/t;y++){
			C[t] = (C[t]+y*cnt2[y*t]%MOD)%MOD;
		}
	}

	ll res = 0;
	for (int t=1;t<=V;t++){
		res = (res+A[t]*B[t]%MOD*C[t]%MOD)%MOD;
	}

	cout << res << '\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	init();
	
	int t;
	cin >> t;
	while (t--) solve();

	return 0;
}