莫比乌斯反演

未完善，瞎看看即可

莫比乌斯函数定义为：

(mu(n)=egin{cases}1&(n=1)\(-1)^r&(n;有且仅有;r;个互不相同的质因子)\0&(其他情况)end{cases})

那么由定义我们可以推出一个性质：

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

证明

显然这是莫比乌斯函数的和函数，所以它也是个乘性函数

对于一个整数 n 我们显然可以将其唯一分解为 (n=p_1^{k_1}p_2^{k_2}dots p_n^{k_n})

所以 (sumlimits_{d|n}mu(d)=sumlimits_{d|p_1^{k_1}}mu(d)sumlimits_{d|p_2^{k_2}}mu(d)dotssumlimits_{d|p_n^{k_n}}mu(d))

而对于一个整数 (m=p^k)

显然 (m=mu(1)+mu(p)+dots+mu(p^k))

(=1+(-1)+0+0+dots+0=0)

所以 (sumlimits_{d|p_1^{k_1}}mu(d)sumlimits_{d|p_2^{k_2}}mu(d)dotssumlimits_{d|p_n^{k_n}}mu(d)=0·0·dots·0=0)

证毕

推论：

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

证明显然

这道题是让我们求：

(sumlimits^n_{i=1}sumlimits^n_{j=1}gcd(i,j))

首先我们可以直接暴力计算，复杂度 (O(n^2))，显然是不可以的

考虑使用莫比乌斯反演，我们发现原式

根据欧拉 (varphi) 函数的性质

(sumlimits_{d|n}varphi(d)=n)

(=sumlimits^n_{i=1}sumlimits^n_{j=1}sumlimits_{d|gcd(i,j)}varphi(d))

枚举 (d)

(=sumlimits^n_{d=1}leftlfloordfrac{n}{d} ight floor^2varphi(d))

直到有一天我看见了一个大佬说可以用狄利克雷卷积做

然后想了两三天，终于会了

原式：

(sumlimits^n_{i=1}sumlimits^n_{j=1}gcd(i,j))

(=sumlimits^n_{d=1}sumlimits^n_{i=1}sumlimits^n_{j=1}[gcd(i,j)=d])

(=sumlimits^n_{d=1}dsumlimits^{leftlfloorfrac{n}{d} ight floor}_{i=1}sumlimits^{leftlfloorfrac{n}{d} ight floor}_{j=1}[gcd(i,j)=1])

(=sumlimits^n_{d=1}dsumlimits^{leftlfloorfrac{n}{d} ight floor}_{i=1}sumlimits^{leftlfloorfrac{n}{d} ight floor}_{j=1}sumlimits_{r|gcd(i,j)}mu(r))

(=sumlimits^n_{d=1}dsumlimits_{r=1}^{leftlfloorfrac{n}{d} ight floor}mu(r)leftlfloordfrac{n}{dr} ight floor^2)

对于 (dr) 我们发现它的取值为 ([1,n]) 于是乎我们试着枚举，看看能不能化简

(=sumlimits^n_{dr=1}leftlfloordfrac{n}{dr} ight floor^2*X)

此时 (X) 对应的是 (dr) 的每个取值后面的取整的那一坨出现的次数

(=sumlimits^n_{dr=1}leftlfloordfrac{n}{dr} ight floor^2sumlimits_{k|dr}kmu(dfrac{dr}{k}))

应用狄利克雷卷积

(=sumlimits^n_{dr=1}leftlfloordfrac{n}{dr} ight floor^2varphi(dr))

此时我们不用管 (d,r) 的具体取值，而只关心他们的乘积

(=sumlimits^n_{k=1}leftlfloordfrac{n}{k} ight floor^2varphi(k))