前置知识

狄利克雷卷积

形如 $f\left(n\right)=\sum _{d\mid n}g\left(d\right)\ast h\left({\displaystyle \frac{n}{d}}\right)$f(n)=d∣n∑​g(d)∗h(dn​)，记作 $f$f是 $g$g 和 $h$h的狄利克雷卷积，记作 $f=g\ast h$f=g∗h。
$eg.$eg. $f\left(n\right)=\sum _{d\mid n}g\left(d\right)\Rightarrow f=g\ast 1$f(n)=d∣n∑​g(d)⇒f=g∗1
$f=f\ast e$f=f∗e， $e$e 为单位函数

狄利克雷卷积的性质

狄利克雷卷积满***换律和结合律，即
$f=g\ast h\ast k=g\ast k\ast h=g\ast (h\ast k)$f=g∗h∗k=g∗k∗h=g∗(h∗k)

进入正题

莫比乌斯函数

定义

定义可以参考其他 $blog$blog (TAT，分段函数实在太难打了)

性质

$\sum _{d\mid n}\mu \left(d\right)=[n=1]$d∣n∑​μ(d)=[n=1]，即是 $\mu \ast 1=e\left(n\right)$μ∗1=e(n)， $e$e 为单位函数。
这是莫比乌斯函数很重要的性质，反演基本基于此。

证明如下：
考虑到每个 $u\left(d\right)$u(d) 对 $ans$ans 贡献只是 $1$1 或 $-1$−1（ $0$0 不用管）
设 $n={\prod }_{i=1}^m{p}_i^{a_i}$n=i=1∏m​piai​​
那么 $n>1$n>1 时 $ans={\sum }_{k=0}^m(-1{)}^k{C}_m^k=(1-1{)}^m=0$ans=k=0∑m​(−1)kCmk​=(1−1)m=0
$n=1$n=1时， $ans=1$ans=1。
证毕。

莫比乌斯反演定理

若有 $f\left(n\right)=\sum _{d\mid n}g\left(d\right)$f(n)=d∣n∑​g(d)，则有 $g\left(n\right)=\sum _{d\mid n}f\left(d\right)\ast \mu \left({\displaystyle \frac{n}{d}}\right)$g(n)=d∣n∑​f(d)∗μ(dn​)

证明如下：
现有 $f=g\ast 1$f=g∗1，则有 $f\ast \mu =g\ast (\mu \ast 1)=g\ast e=g$f∗μ=g∗(μ∗1)=g∗e=g（这是狄利克雷卷积的证法，当然还有其他证法，可参考其他 $blog$blog）

莫比乌斯函数的应用

①：让我们先来考虑下面一道最最最经典的题：

求 ans=i=1∑n​j=1∑m​[gcd(i,j)==1](n<m)
解：考虑到 $\left[gcd\right(i,j)==1]$[gcd(i,j)==1] 是单位函数， 而 $e=\mu \ast 1$e=μ∗1，于是
$ans={\sum }_{i=1}^n{\sum }_{j=1}^m\sum _{d\mid gcd(i,j)}\mu \left(d\right)={\sum }_{i=1}^n{\sum }_{j=1}^m\sum _{d\mid i,d\mid j}\mu \left(d\right)$ans=i=1∑n​j=1∑m​d∣gcd(i,j)∑​μ(d)=i=1∑n​j=1∑m​d∣i,d∣j∑​μ(d)
考虑每个 $\mu \left(d\right)$μ(d) 出现了多少次，则有
$ans={\sum }_{d=1}^n\mu \left(d\right)\ast \lfloor {\displaystyle \frac{n}{d}}\rfloor \ast \lfloor {\displaystyle \frac{m}{d}}\rfloor$ans=d=1∑n​μ(d)∗⌊dn​⌋∗⌊dm​⌋，然后用除法分块，可以使复杂度达到 $O\left(\sqrt{n}\right)$O(n ​)

②：进阶版

求 ans=i=1∑n​j=1∑m​gcd(i,j)(n<m)
枚举 $d=gcd(i,j)$d=gcd(i,j)，有
$ans={\sum }_{d=1}^{n}d{\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i/d,j/d)==1]={\sum }_{d=1}^{n}d{\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }{\sum }_{j=1}^{\lfloor {\displaystyle \frac{m}{d}}\rfloor }\left[gcd\right(i,j)==1]={\sum }_{d=1}^{n}d{\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }{\sum }_{j=1}^{\lfloor {\displaystyle \frac{m}{d}}\rfloor }\sum _{k\mid i,k\mid j}\mu \left(k\right)={\sum }_{d=1}^{n}d{\sum }_{k=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }\mu \left(k\right)\lfloor {\displaystyle \frac{n}{kd}}\rfloor \lfloor {\displaystyle \frac{m}{kd}}\rfloor$ans=d=1∑n​di=1∑n​j=1∑m​[gcd(i/d,j/d)==1]=d=1∑n​di=1∑⌊dn​⌋​j=1∑⌊dm​⌋​[gcd(i,j)==1]=d=1∑n​di=1∑⌊dn​⌋​j=1∑⌊dm​⌋​k∣i,k∣j∑​μ(k)=d=1∑n​dk=1∑⌊dn​⌋​μ(k)⌊kdn​⌋⌊kdm​⌋，然后 $\lfloor {\displaystyle \frac{n}{d}}\rfloor$⌊dn​⌋分块， $\lfloor {\displaystyle \frac{n}{kd}}\rfloor$⌊kdn​⌋分块。
复杂度是 $O(\sqrt{n}\ast \sqrt{n}=n)$O(n ​∗n ​=n)

③：再进阶一点点

这题是 $bzoj2154$bzoj 2154 Crash的数字表格 / JZPTAB
求 $ans={\sum }_{i=1}^n{\sum }_{j=1}^{m}lcm(i,j)$ans=i=1∑n​j=1∑m​lcm(i,j)
众所周知， $lcm(i,j)={\displaystyle \frac{i\ast j}{gcd(i,j)}}$lcm(i,j)=gcd(i,j)i∗j​，于是
$ans={\sum }_{i=1}^n{\sum }_{j=1}^m{\displaystyle \frac{i\ast j}{gcd(i,j)}}={\sum }_{d=1}^n{\sum }_{i=1}^n{\sum }_{j=1}^m{\displaystyle \frac{i\ast j}{d}}\ast \left[gcd\right(i,j)==d]={\sum }_{d=1}^n{\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }{\sum }_{j=1}^{\lfloor {\displaystyle \frac{m}{d}}\rfloor }ijd\left[gcd\right(i,j)==1]={\sum }_{d=1}^{n}d{\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }{\sum }_{j=1}^{\lfloor {\displaystyle \frac{m}{d}}\rfloor }ij\sum _{k\mid i,k\mid j}\mu \left(k\right)$ans=i=1∑n​j=1∑m​gcd(i,j)i∗j​=d=1∑n​i=1∑n​j=1∑m​di∗j​∗[gcd(i,j)==d]=d=1∑n​i=1∑⌊dn​⌋​j=1∑⌊dm​⌋​ijd[gcd(i,j)==1]=d=1∑n​di=1∑⌊dn​⌋​j=1∑⌊dm​⌋​ijk∣i,k∣j∑​μ(k)，然后考虑枚举 $k$k，有
$ans={\sum }_{d=1}^{n}d{\sum }_{k=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }\mu \left(k\right)\ast k^2{\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{kd}}\rfloor }i{\sum }_{j=1}^{\lfloor {\displaystyle \frac{m}{kd}}\rfloor }j$ans=d=1∑n​dk=1∑⌊dn​⌋​μ(k)∗k2i=1∑⌊kdn​⌋​ij=1∑⌊kdm​⌋​j，然后两个整除分块即可，复杂度 $O\left(n\right)$O(n)

代码如下

#include <bits/stdc++.h>
#define N 10000005
#define LL long long
#define mod 20101009
using namespace std;
int p[N], cnt, mu[N], s[N], g[N]; 
bool x[N];
LL z = 1, t;
int main(){
	int i, j, n, m, l1, l2, r1, r2, sum, ans, a, b;
	scanf("%d%d", &n, &m);
	if(n > m) swap(n, m);
	mu[1] = 1;
	for(i = 2; i <= m; i++){
		if(!x[i]) x[i] = 1, p[++cnt] = i, mu[i] = -1;
		for(j = 1; j <= cnt; j++){
			t = z * i * p[j];
			if(t > m) break;
			x[t] = 1;
			if(i % p[j] == 0) break;
			mu[t] = -mu[i];
		}
	}
	for(i = 1; i <= m; i++) g[i] = (g[i - 1] + i) % mod, s[i] = (s[i - 1] + z * mu[i] * i * i % mod + mod) % mod;
	ans = sum = 0;
	for(l1 = 1; l1 <= n; l1 = r1 + 1){
		j = n / l1; r1 = min(n / (n / l1), m / (m / l1));
		a = n / l1, b = m / l1;
		sum = 0;
		for(l2 = 1; l2 <= j; l2 = r2 + 1){
			r2 = min(a / (a / l2), b / (b / l2));
			sum = (sum + z * (s[r2] - s[l2 - 1]) * g[a / l2] % mod * g[b / l2] % mod) % mod;
		}
		ans = (ans + z * sum * (g[r1] - g[l1 - 1]) % mod) % mod;
	}
	printf("%d", (ans + mod) % mod);
	return 0;
}

④ 再进阶一点点

求 ans=i=1∑n​j=1∑m​[gcd(i,j)∈prime](n<m)
考虑枚举 $n$n 以内的素数，于是有
$ans=\sum _p{\sum }_{i=1}^n{\sum }_{j=1}^m\left[gcd\right(i,j)==p]=\sum _p{\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{p}}\rfloor }{\sum }_{j=1}^{\lfloor {\displaystyle \frac{m}{p}}\rfloor }\left[gcd\right(i,j)==1]=\sum _p{\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{p}}\rfloor }{\sum }_{j=1}^{\lfloor {\displaystyle \frac{m}{p}}\rfloor }\sum _{k\mid i,k\mid j}\mu \left(k\right)=\sum _p{\sum }_{k=1}^{\lfloor {\displaystyle \frac{n}{p}}\rfloor }\mu \left(k\right)\lfloor {\displaystyle \frac{n}{kp}}\rfloor \lfloor {\displaystyle \frac{m}{kp}}\rfloor$ans=p∑​i=1∑n​j=1∑m​[gcd(i,j)==p]=p∑​i=1∑⌊pn​⌋​j=1∑⌊pm​⌋​[gcd(i,j)==1]=p∑​i=1∑⌊pn​⌋​j=1∑⌊pm​⌋​k∣i,k∣j∑​μ(k)=p∑​k=1∑⌊pn​⌋​μ(k)⌊kpn​⌋⌊kpm​⌋

操作来了！！

我们考虑枚举 $T=kp$T=kp，于是有
$ans={\sum }_{T=1}^n\lfloor {\displaystyle \frac{n}{T}}\rfloor \lfloor {\displaystyle \frac{m}{T}}\rfloor \sum _{p\mid T}\mu \left({\displaystyle \frac{T}{p}}\right)$ans=T=1∑n​⌊Tn​⌋⌊Tm​⌋p∣T∑​μ(pT​)
对于后面那部分，我们可以预处理，将每个素数的倍数 $i$i 加上 $\mu \left(i\right)$μ(i)，复杂度是 $O\left(wln\right(w\left)\right)$O(wln(w))， $w$w 为素数个数，而 $w$w 大约是 ${\displaystyle \frac{n}{ln\left(n\right)}}$ln(n)n​，所以总的复杂度是 $O\left(n\right)$O(n)，单次询问的复杂度为 $O\left(\sqrt{n}\right)$O(n ​)

暂时就写这么多吧