一、莫比乌斯函数

1. 定义

若 $n=p_1^{t_1}{p}_2^{t_2}{p}_3^{t_3}\dots p_k^{t_k}$，其中 $p_i$ 是 $n$ 的互异质因子。

$\mu (n)=\{\begin{array}{cc}(-1{)}^q& t_i=1\\ 1& n=1\\ 0& \text{Otherwise.}\end{array}$

2. 性质

性质一

若$n\ne 1$，则 $\sum _{d|n}\mu (d)=0$。

设 $n=p_1^{t_1}{p}_2^{t_2}{p}_3^{t_3}\dots p_k^{t_k}$，其中 $p_i$ 是 $n$ 的互异质因子。

因为 $d|n$，所以 $d$ 是由 $n$ 的质因子中选择若干个相乘得到的。

如果 $d$ 是由一个以上相同的质因子组成的，则 $\mu (d)=0$，所以只有在 $p_1$ 到 $p_q$ 间选择若干个组成 $d$，才会对答案有贡献。

若选择 $i$ 个质因子，则方案数为 $C_q^i$，贡献为 $(-1{)}^i{C}_q^i$。

所以：

$$\sum _{d|n}\mu (d)=\sum _{i=0}^q(-1{)}^i{C}_q^i$$

将 $x=-1$ 代入 $(x+1{)}^n=\sum _{i=0}^n{x}^i{C}_n^i$，有：

$$\sum _{i=0}^q(-1{)}^i{C}_q^i=0$$

性质二

$\mu (x)$ 是积性函数。

若 $a$ 和 $b$ 互质，且 $a$ 的质因子后有 $p$ 项，$b$ 的有 $q$ 项。

当 $\mu (a)$ 与 $\mu (b)$ 均不为 $0$ 时，那么明显 $ab$ 的质因子有 $p+q$ 项，因为 $(-1{)}^{p+q}=(-1{)}^p(-1{)}^q$，所以 $\mu (ab)=\mu (a)\mu (b)$。

当 $\mu (a)$ 与 $\mu (b)$ 至少有一项为 $0$ 时，那么明显 $ab$ 也会有重复的质因子，所以 $\mu (ab)=0=\mu (a)\mu (b)$。

二、莫比乌斯反演的套路

没有算法，全是套路。

1. P3455 [POI2007] ZAP-Queries

求式子：

$$\sum _{i=1}^a\sum _{j=1}^b[gcd(i,j)=d]$$

为书写简便，假设式子中的 $a\le b$。下文中的 $x/y$ 均表示 $\lfloor \frac{x}{y}\rfloor$。

套路一

将 $gcd(i,j)=d$ 化为 $gcd(i,j)=1$。

全部同时除以 $d$ 即可。

$$\sum _{i=1}^{a/d}\sum _{j=1}^{b/d}[gcd(i,j)=1]$$

套路二

运用莫比乌斯函数的性质一转换。

由性质一，可得若 $n=1$，则 $\sum _{d|n}\mu (d)=1$，所以，将 $[gcd(i,j)=1]$ 转换一下：

$$\sum _{i=1}^{a/d}\sum _{j=1}^{b/d}\sum _{x|gcd(i,j)}\mu (x)$$

套路三

将 $x$ 的和号改为枚举 $x$ 的形式。

因为 $x\le gcd(i,j)$，所以 $x\le min(a/d,b/d)$，如果 $x|gcd(i,j)$，那么 $[x|gcd(i,j)]=1$，所以：

$$\sum _{i=1}^{a/d}\sum _{j=1}^{b/d}\sum _{x=1}^{a/d}\mu (x)[x|gcd(i,j)]$$

套路四

让每个函数都只和他前面的和号有关系。

容易发现 $\mu (x)$ 和前两个和号没有半毛钱关系，直接提前，所以：

$$\sum _{x=1}^{a/d}\mu (x)\sum _{i=1}^{a/d}\sum _{j=1}^{b/d}[x|gcd(i,j)]$$

套路五

把判断整除 $gcd$ 拆开。

容易发现 $[x|gcd(i,j)]$ 一部分等价于 $[x|i\wedge x|j]$，也就是 $[x|i][x|j]$：

$$\sum _{x=1}^{a/d}\mu (x)\sum _{i=1}^{a/d}\sum _{j=1}^{b/d}[x|i][x|j]$$

此时再用一下套路四：

$$\sum _{x=1}^{a/d}\mu (x)\sum _{i=1}^{a/d}[x|i]\sum _{j=1}^{b/d}[x|j]$$

套路六

把判断整除拆开。

$\sum _{i=1}^{a/d}[x|i]$ 就是求 $1\sim a/d$ 中，$x$ 的倍数的个数，明显可以直接用 $a/d/x$ 求出，所以：

$$\sum _{x=1}^{a/d}\mu (x)(a/d/x)(b/d/x)$$

至此，化简完成，$\sum _{x=1}^{a/d}\mu (x)$ 可以用前缀和求出，后面的部分可以用整除分块求出。

Code:

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e5+10;
int n,a,b,c,d,k,ans,q[N];
namespace Mu{
	int prime[N],tot,mu[N];
	bool isprime[N];
	void getmu(int x){
		memset(isprime,true,sizeof isprime);
		isprime[1]=false;
		mu[1]=1;
		for(int i=2;i<=x;i++){
			if(isprime[i]){
				prime[++tot]=i;
				mu[i]=-1;
			}
			for(int j=1;j<=tot and i*prime[j]<=x;j++){
				isprime[i*prime[j]]=false;
				if(!(i%prime[j]))break;
				mu[i*prime[j]]=-mu[i];
			}
		}
	}
}using namespace Mu;
signed main(){
	IOS;
	getmu(5e4);
	for(int i=1;i<=5e4;i++)
		q[i]=q[i-1]+mu[i];
	
	cin>>n;
	while(n--){
		cin>>a>>b>>k;
		a/=k;
		b/=k;
		if(a>b)swap(a,b);
		ans=0;
		for(int l=1,r;l<=a;l=r+1){
			r=min(a/(a/l),b/(b/l));
			ans+=(q[r]-q[l-1])*(a/l)*(b/l);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

2. P4449 于神之怒加强版

求式子：

$$\sum _{i=1}^n\sum _{j=1}^{m}gcd(i,j{)}^k$$

套路七

将求值部分改为枚举取值并乘上合法个数。

显然的，上面的式子可以枚举 $gcd(i,j)$ 的值，假设 $d=gcd(i,j)$，那么就可以化简为：

$$\sum _{i=1}^n\sum _{j=1}^m\sum _{d=1}^n{d}^k[gcd(i,j)=d]$$

此时，运用套路四：

$$\sum _{d=1}^n{d}^k\sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)=d]$$

发现后半部分跟上一题一模一样，直接运用上一题相同的方法化简：

$$\sum _{d=1}^n{d}^k\sum _{x=1}^{n/d}\mu (x)(n/d/x)(m/d/x)$$

套路八

运用向上/下取整的性质化简。

性质：

$$\lfloor \frac{a}{\lfloor \frac{b}{c}\rfloor }\rfloor =\lfloor \frac{a}{bc}\rfloor ,\lceil \frac{a}{\lceil \frac{b}{c}\rceil }\rceil =\lceil \frac{a}{bc}\rceil$$

所以：

$$\sum _{d=1}^n{d}^k\sum _{x=1}^{n/d}\mu (x)(n/(dx))(m/(dx))$$

套路九

分母出现两个枚举的数的积时，改为枚举这个积。

令 $T=dx$，所以：

$$\sum _{T=1}^n(n/T)(m/T)\sum _{d|T}{d}^k\mu (\frac{T}{d})$$

此时，只要求出后半部分 $\sum _{d|T}{d}^k\mu (\frac{T}{d})$ 就好了。

设 $f(T)=\sum _{d|T}{d}^k\mu (\frac{T}{d})$，很容易可以得到这是一个积性函数，所以将 $T$ 分解质因子，$T=p_1^{t_1}{p}_2^{t_2}{p}_3^{t_3}\dots p_q^{t_q}$，那么由积性函数的性质：

$$f(T)=\prod _{i=1}^{q}f(p_i^{t_i})=\prod _{i=1}^q{p}_i^{k(t_i-1)}\mu (p_i)+p_i^{k{t}_i}\mu (1)=\prod _{i=1}^q{p}_i^{k(t_i-1)}+p_i^{k{t}_i}$$

于是就可以线性筛了，原式变为：

$$\sum _{T=1}^n(n/T)(m/T)f(T)$$

使用整除分块解决。

3. P1829 [国家集训队] Crash的数字表格 / JZPTAB

求式子：

$$\sum _{i=1}^n\sum _{j=1}^m\text{lcm}(i,j)$$

运用 $\text{lcm}(a,b)=\frac{ab}{gcd(a,b)}$ 的关系，很容易可以得到：

$$\sum _{i=1}^n\sum _{j=1}^m\frac{ij}{gcd(i,j)}$$

运用套路七：

$$\sum _{d=1}^n\sum _{i=1}^n\sum _{j=1}^{m}ij/d[gcd(i,j)=d]$$

运用套路一，但是出现了一个没见过的 $ij/d$，设 $i^{\prime }=i/d,j^{\prime }=j/d$，则：

$$ij/d=i^{\prime }d{j}^{\prime }d/d=i^{\prime }{j}^{\prime }d$$

所以：

$$\sum _{d=1}^n\sum _{i=1}^{n/d}\sum _{j=1}^{m/d}ijd[gcd(i,j)=1]$$

运用套路二；

$$\sum _{d=1}^n\sum _{i=1}^{n/d}\sum _{j=1}^{m/d}\sum _{x|gcd(i,j)}ijd\mu (x)$$

运用套路三：

$$\sum _{d=1}^n\sum _{i=1}^{n/d}\sum _{j=1}^{m/d}\sum _{x=1}^{n/d}ijd\mu (x)[x|gcd(i,j)]$$

运用套路四：

$$\sum _{d=1}^{n}d\sum _{x=1}^{n/d}\mu (x)\sum _{i=1}^{n/d}\sum _{j=1}^{m/d}ij[x|gcd(i,j)]$$

运用套路五：

$$\sum _{d=1}^{n}d\sum _{x=1}^{n/d}\mu (x)\sum _{i=1}^{n/d}\sum _{j=1}^{m/d}ij[x|i][x|j]$$

套路十

将整除中的除数化为 $1$。

因为 $[1|p]=1$，所以这样做可以直接化简掉 $[x|p]$ 这样的东西，所以我们在和号的边界里除掉一个 $x$，再在求值里乘回一个 $x$：

$$\sum _{d=1}^{n}d\sum _{x=1}^{n/d}\mu (x)\sum _{i=1}^{n/d/x}\sum _{j=1}^{m/d/x}ij{x}^2[1|i][1|j]$$$$\sum _{d=1}^{n}d\sum _{x=1}^{n/d}\mu (x)\sum _{i=1}^{n/d/x}\sum _{j=1}^{m/d/x}ij{x}^2$$

再次运用套路四：

$$\sum _{d=1}^{n}d\sum _{x=1}^{n/d}\mu (x)x^2\sum _{i=1}^{n/d/x}i\sum _{j=1}^{m/d/x}j$$

后面两个和号明显就是一个等差数列，直接变成式子：

$$\sum _{d=1}^{n}d\sum _{x=1}^{n/d}\mu (x)x^2\frac{(1+n/d/x)(n/d/x)}{2}\frac{(1+m/d/x)(m/d/x)}{2}$$

化简完成，但是这式子也太抽象了，根本没法求，想办法通过用多几个函数来表示方便一点：

观察到第二个和号开始后面的部分可以用整除分块求，那么定义一个函数 $f(p,q)$ 表示该部分：

$$f(p,q)=\sum _{x=1}^p\mu (x)x^2\frac{(1+p/x)(p/x)}{2}\frac{(1+q/x)(q/x)}{2}$$

观察到最后的两个分式可以 $O(1)$ 求，那么定义一个函数 $g(p,q)$ 表示该部分：

$$g(p,q)=\frac{p(p+1)}{2}\frac{q(q+1)}{2}$$$$f(p,q)=\sum _{x=1}^p\mu (x)x^{2}g(p/x,q/x)$$$$ans=\sum _{d=1}^{n}df(n/d,m/d)$$

使用整除分块解决。

4. P3312 [SDOI2014] 数表