莫比乌斯反演

数论函数

定义域为正整数、陪域为复数的函数

(phi(x))，欧拉函数

也写作：(varphi(x))

含义：小于等于自己的，与自己互质的数的个数

通式：(phi(x)=xprodlimits_{p_i}(1-dfrac{1}{p_i}))，其中(p_i)为(x)的质因数

特殊性质：

[sumlimits_{i|n}phi(i)=n ]

举个栗子证明理解一下：

(12)个分数

[dfrac{1}{12},dfrac{2}{12},dfrac{3}{12},dfrac{4}{12},dfrac{5}{12},dfrac{6}{12},dfrac{7}{12},dfrac{8}{12},dfrac{9}{12},dfrac{10}{12},dfrac{11}{12},dfrac{12}{12} ]

约分一下

[dfrac{1}{12},dfrac{1}{6},dfrac{1}{4},dfrac{1}{3},dfrac{5}{12},dfrac{1}{2},dfrac{7}{12},dfrac{2}{3},dfrac{3}{4},dfrac{5}{6},dfrac{11}{12},dfrac{1}{1} ]

按分母分个类

[{dfrac{1}{1}},{dfrac{1}{2}},{dfrac{1}{3},dfrac{2}{3}},{dfrac{1}{4},dfrac{3}{4}},{dfrac{1}{6},dfrac{5}{6}},{dfrac{1}{12},dfrac{5}{12},dfrac{7}{12},dfrac{11}{12}} ]

[12=phi(1)+phi(2)+phi(3)+phi(4)+phi(6)+phi(12) ]

(mu(x))，莫比乌斯函数

[mu(x)=egin{cases}1(x=1)\(-1)^k ( ext{$x$没有平方数因数，且$x$的质因数个数为$k$，即$x=prodlimits_{p_iin prime} p_i$})\0 ( ext{$x$有平方数因数})end{cases} ]

特殊性质：

[sumlimits_{i|n}mu(i)=[n=1] ]

(epsilon(x))，元函数

[epsilon(x)=[x=1] ]

(id(x))，单位函数

[id(x)=x ]

(I(x))，恒等函数

[I(x)=1 ]

也记作(1(x)=1)

积性函数

积性函数：对于任意互质的整数(a)和(b)，都有(f(ab)=f(a)cdot f(b))的函数(f)，(f(1)=1)

完全积性函数：对于任意整数(a)和(b) ，都有(f(ab)=f(a)cdot f(b))的函数(f)

以上提到的所有函数均为积性函数，其中(phi,mu)为积性函数，(epsilon,id,I)为完全积性函数

利用积性函数的性质，我们可以进行线性筛

狄利克雷卷积

定义两个数论函数的狄利克雷卷积(otimes(ast))

若$h=fast g $

[h(n)=sumlimits_{i|n}f(i)g(dfrac{n}{i}) ]

一定要记住这个式子

以下性质（看看就好）：

1. 交换律：(fast g=gast f)
2. 结合律：(fast (gast h)=(fast g)ast h)
3. 分配律：((f+g)ast h=f ast h+gast h)
4. ((xf)ast g=x(fast g))
5. (epsilonast f=f)

将上述(phi)和(mu)的性质用卷积形式表示，就是

[sumlimits_{i|n}phi(i)=niff phi ast I = id ]

[sumlimits_{i|n}mu(i)=[n=1]iff mu ast I=epsilon ]

莫比乌斯反演

[g=fast I ]

两边同时卷一个(mu)

[gast mu=fast Iast mu=fast epsilon=f ]

（这步转化注意使用狄利克雷卷积的性质）

[g=fast Iiff gast mu=f ]

用式子表示，就是

[g(n)=sumlimits_{i|n}f(i)iff f(n)=sumlimits_{i|n}mu(dfrac{n}{i})g(i) ]

这个式子就是莫比乌斯反演

应用

（以下式子可以用莫比乌斯反演推，但是我懒）

求

[sumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)=1] ]

[ecause[gcd(i,j)=1]=epsilon(gcd(i,j))=sumlimits_{d|gcd}mu(d) ]

[ ext{原式}=sumlimits_{i=1}^nsumlimits_{j=1}^msumlimits_{d|gcd}mu(d) ]

先枚举(d)，即(gcd)的因数

[ ext{原式}=sumlimits_{d=1}^{min(n,m)}mu(d)sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[d|gcd(i,j)] ]

[=sumlimits_{d=1}^{min(n,m)}mu(d)sumlimits_{i=1}^{leftlfloorfrac{n}{d} ight floor}sumlimits_{j=1}^{leftlfloorfrac{m}{d} ight floor}1 ]

[=sumlimits_{d=1}^{min(n,m)}mu(d)leftlfloorfrac{n}{d} ight floorleftlfloorfrac{m}{d} ight floor ]

注意到(leftlfloordfrac{n}{d} ight floor)只有(sqrt n)种取值，整除分块((O(sqrt n)))加上预处理(mu(O(n)))，可以处理多组询问

整除分块

• 在(i)到(leftlfloordfrac{n}{leftlfloordfrac{n}{i} ight floor} ight floor)这个范围内，(leftlfloordfrac{n}{i} ight floor)的值是一样的，(i)取到(leftlfloordfrac{n}{leftlfloordfrac{n}{i} ight floor} ight floor+1)时，(leftlfloordfrac{n}{i} ight floor)的值会变小

• (leftlfloordfrac{n}{d} ight floor)只有(sqrt n)种取值

利用这个就可以做整除分块了

对于这个式子(sumlimits_{d=1}^{min(n,m)}mu(d)leftlfloorfrac{n}{d} ight floorleftlfloorfrac{m}{d} ight floor)

在(i-min(leftlfloordfrac{n}{leftlfloorfrac{n}{i} ight floor} ight floor,leftlfloordfrac{m}{leftlfloorfrac{m}{i} ight floor} ight floor))的范围内，(leftlfloordfrac{n}{d} ight floorleftlfloordfrac{m}{d} ight floor)的值不变

设 (r=min(leftlfloordfrac{n}{leftlfloorfrac{n}{i} ight floor} ight floor,leftlfloordfrac{m}{leftlfloorfrac{m}{i} ight floor} ight floor))

那么这一段内的和就是(leftlfloordfrac{n}{d} ight floorleftlfloordfrac{m}{d} ight floorcdot sumlimits_{j=i}^{r}mu(j))

对(mu)求一下前缀和，即可(O(1))算出(i-r)的和

inline long long solve(int n,int m){
	long long ans=0;
	for(int i=1,r;i<=min(n,m);i=r+1){
		r=min(n/(n/i),m/(m/i));
		ans+=1ll*(n/i)*(m/i)*(musum[r]-musum[i-1]);
	}
	return ans;
}