莫比乌斯反演 - 进阶

莫比乌斯反演推论

如果

$$f(d)=\sum_{d|i,i\le n}g(i)$$

那么

$$g(d)=\sum_{d|i,i\le n}f(i)\mu\left(\frac{i}{d}\right)$$

YY 的 GCD

设$f(i)$表示$i$是否是质数。求

$$\sum_{i=1}^n\sum_{j=1}^mf(\gcd(i,j))$$

多组询问，$n,m\le 10^7,T\le 10000$。

原式为

$$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^mf(\gcd(i,j))\\ =&\sum_{d=1}^{\min(n,m)}f(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum_{p|i,p|j}\mu(p)\\ =&\sum_{d=1}^{\min(n,m)}f(d)\sum_{p=1}^{\left\lfloor\frac{\min(n,m)}{d}\right\rfloor}\mu(p) \left\lfloor\frac{n}{dp}\right\rfloor\left\lfloor\frac{m}{dp}\right\rfloor\\ =&\sum_{T=1}^{\min(n,m)}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum_{d|T}f(d)\mu\left(\frac{T}{d}\right) \end{aligned}$$

设

$$h(T)=\sum_{d|T}f(d)\mu\left(\frac{T}{d}\right)$$

由于$h$大多数项都是 0，因此只需要预处理不是 0 的项，再做一个前缀和即可。

代码

LOJ6686 Stupid GCD

求

$$\sum_{i=1}^n\gcd(\left\lfloor \sqrt[3]{i} \right\rfloor,i)$$

$n\le 10^{30}$。

首先可以转化为枚举$\left\lfloor \sqrt[3]{i} \right\rfloor$：

$$\begin{aligned} &\sum_{i=1}^n\gcd(\left\lfloor \sqrt[3]{i} \right\rfloor,i)\\ =&\sum_{i=1}^{\left\lfloor \sqrt[3]{n} \right\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}\gcd(i,j) + \sum_{i=\left\lfloor \sqrt[3]{n} \right\rfloor^3}^n\gcd(\left\lfloor \sqrt[3]{n} \right\rfloor,i)\\ \end{aligned}$$

第一部分

$$\begin{aligned} &\sum_{i=1}^{\left\lfloor \sqrt[3]{n} \right\rfloor-1}\sum_{j=i^3}^{(i+1)^3-1}\gcd(i,j) \\ =&\sum_{i=1}^{\left\lfloor \sqrt[3]{n} \right\rfloor-1}\sum_{j=0}^{3i^2+3i}\gcd(i,j) \\ =&\sum_{i=1}^{\left\lfloor \sqrt[3]{n} \right\rfloor-1}i+(3i+3)\sum_{j=1}^{i}\gcd(i,j) \end{aligned}$$

化简后面的部分：

$$\begin{aligned} &\sum_{j=1}^{i}\gcd(i,j)\\ =&\sum_{d|i}d\sum_{j=1}^{\frac{i}{d}}\left[\gcd\left(\frac{i}{d},j\right)=1\right]\\ =&\sum_{d|i}d\cdot \varphi\left(\frac{i}{d}\right) \end{aligned}$$

那么可以得到

$$\begin{aligned} &\sum_{i=1}^{\left\lfloor \sqrt[3]{n} \right\rfloor-1}i+(3i+3)\sum_{j=1}^{i}\gcd(i,j)\\ =&\sum_{i=1}^{\left\lfloor \sqrt[3]{n} \right\rfloor-1}(3i+3)\sum_{d|i}d\cdot \varphi\left(\frac{i}{d}\right) +\sum_{i=1}^{\left\lfloor \sqrt[3]{n}-1 \right\rfloor}i\\ =&\sum_{d=1}^{\left\lfloor \sqrt[3]{n} \right\rfloor-1} d \sum_{i=1}^{\left\lfloor\frac{\left\lfloor \sqrt[3]{n} \right\rfloor-1}{d}\right\rfloor} (3id+3)\varphi(i) \end{aligned}$$

这显然可以分块了。

第二部分

$$\begin{aligned} &\sum_{i=\left\lfloor \sqrt[3]{n} \right\rfloor^3}^n\gcd(\left\lfloor \sqrt[3]{n} \right\rfloor,i)\\ =&\sum_{i=0}^{n-\left\lfloor \sqrt[3]{n} \right\rfloor^3}\gcd(\left\lfloor \sqrt[3]{n} \right\rfloor,i)\\ \end{aligned}$$

那么可以得到

$$\begin{aligned} g(x,n)=&\sum_{i=1}^n\gcd(x,i)\\ =&\sum_{d|x}d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\left[\gcd\left(\frac{x}{d},i\right)=1\right]\\ =&\sum_{d|x}d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{p|\frac{x}{d},p|i}\mu(p)\\ =&\sum_{T|x}\sum_{d|T}d\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\mu\left(\frac{T}{d}\right)\\ =&\sum_{T|x}\left\lfloor\frac{n}{T}\right\rfloor\varphi(T) \end{aligned}$$

于是原式即为$g(\left\lfloor \sqrt[3]{n} \right\rfloor,n-\left\lfloor \sqrt[3]{n} \right\rfloor^3)+\left\lfloor \sqrt[3]{n} \right\rfloor$。

两个部分使用杜教筛处理$\varphi,\varphi\cdot ID$的前缀和即可。时间复杂度$O(n^{\frac{2}{9}})$。

代码

NOI2016 循环之美

$$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]\\ =&\sum_{j=1}^m[j\perp k]\sum_{i=1}^n[i\perp j]\\ =& \sum_{j=1}^m[j\perp k]\sum_{i=1}^n\sum_{d|i,d|j}\mu(d)\\ =& \sum_{j=1}^m[j\perp k]\sum_{d|j,d\le n}\left\lfloor\frac{n}{d}\right\rfloor\mu(d)\\ =& \sum_{d=1}^n\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[jd\perp k]\\ =& \sum_{d=1}^n\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[j\perp k][d\perp k]\\ =& \sum_{d=1}^n\mu(d)\left\lfloor\frac{n}{d}\right\rfloor[d\perp k]\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[j\perp k]\\ \end{aligned}$$

第一部分

设

$$f(x)=\sum_{j=1}^x[j\perp k]$$

则

$$f(x)=\varphi(k)\left\lfloor\frac{x}{k}\right\rfloor+f(x\bmod k)$$

对于$f(x),x\in[0,k-1]$，我们暴力求一下即可。

原式化为

$$\sum_{i=1}^n\mu(i)[i\perp k] \left\lfloor\frac{n}{i}\right\rfloor f\left(\left\lfloor\frac{m}{i}\right\rfloor\right)$$

第二部分

后面的做分块，考虑算前面的前缀和。设

$$\begin{aligned} g(n,k)=&\sum_{i=1}^n\mu(i)[i\perp k]\\ =&\sum_{i=1}^n\mu(i)\sum_{d|i,d|k}\mu(d)\\ =&\sum_{d|k}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(id)\\ =&\sum_{d|k}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(i)\mu(d)[i\perp d]\\ =&\sum_{d|k}\mu^2(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(i)[i\perp d]\\ =&\sum_{d|k}\mu^2(d)g\left(\left\lfloor\frac{n}{d}\right\rfloor,d\right) \end{aligned}$$

递归下去即可，边界$g(n,1)=\sum_{i=1}^n\mu(i)$。

代码

Luogu5348 密码解锁

已知

$$\sum_{d|x,x\le n}f(x)=\mu(d)$$

求$f(m)$。$m\le 10^9,\frac{n}{m}\le 10^9$。

第一部分

由莫比乌斯反演推论可以得到

$$\begin{aligned} f(m)=&\sum_{m|i,i\le n}\mu(i)\mu\left(\frac{i}{m}\right)\\ =&\sum_{i=1}^{\left\lfloor\frac{n}{m}\right\rfloor}\mu(im)\mu\left(i\right)\\ =&\sum_{i=1}^{\left\lfloor\frac{n}{m}\right\rfloor}\mu^2(i)\mu(m)[i\perp m]\\ =&\mu(m)\sum_{i=1}^{\left\lfloor\frac{n}{m}\right\rfloor}\mu^2(i)[i\perp m] \end{aligned}$$

第二部分

考虑把这个和式做一个递归：

$$\begin{aligned} g(n,k)=&\sum_{i=1}^n\mu^2(i)[i\perp k]\\ =&\sum_{i=1}^n\mu^2(i)\sum_{d|i,d|k}\mu(d)\\ =&\sum_{d|k}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu^2(id)\\ =&\sum_{d|k}\mu^3(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu^2(i)[i\perp d]\\ =&\sum_{d|k}\mu(d)g\left(\left\lfloor\frac{n}{d}\right\rfloor,d\right) \end{aligned}$$

第三部分

边界为$g(n,1)=\sum_{i=1}^n\mu^2(i)$。

我们考虑$\mu^2(i)$的贡献。当且仅当$i$不含平方及以上的因子时，$\mu^2(i)=1$，否则$\mu^2(i)=0$。

因此我们要求$1\sim n$中无平方因子的数的个数。那么考虑容斥，用整体减掉含有平方因子的数：

$$\sum_{i=1}^n\mu^2(i)=n+\sum_{i=2}^n\mu(i)\left\lfloor \frac{n}{i^2} \right\rfloor\\=\sum_{i=1}^n\mu(i)\left\lfloor \frac{n}{i^2} \right\rfloor=\sum_{i=1}^{\sqrt{n}}\mu(i)\left\lfloor \frac{n}{i^2} \right\rfloor$$

$\mu(i)$是容斥系数。注意在实现的时候不一定要直接前缀和。因为$\mu(i)$只有在无重复因子的时候才有值，因此可以 DFS。

原式为$\mu(m)g\left(\left\lfloor\dfrac{n}{m}\right\rfloor,m\right)$。计算即可。复杂度能过。

代码

HDU4944 FSF’s game

求

$$\sum_{i=1}^n\sum_{j=i}^n\sum_{k|i,k|j}\frac{ij}{\gcd\left(\frac{i}{k},\frac{j}{k}\right)}$$

多组数据，$T,n\le 5\times 10^5$。

第一部分

$$\begin{aligned} &\sum_{i=1}^n\sum_{j=i}^n\sum_{k|i,k|j}\frac{ij}{\gcd\left(\frac{i}{k},\frac{j}{k}\right)}\\ =&\sum_{k=1}^nk^2\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=i}^{\lfloor\frac{n}{k}\rfloor}\operatorname{lcm}(i,j) \end{aligned}$$

设$f(n)=\sum_{i=1}^n\sum_{j=i}^n\operatorname{lcm}(i,j)=\sum_{j=1}^n\sum_{i=1}^j\operatorname{lcm}(i,j)$。

设$g(n)=\sum_{i=1}^n\gcd(n,i)$。那么可以套路反演得到

$$g(n)=\frac{1}{2}n\left[\left(\sum_{d|n}d\cdot \varphi(d)\right)-1\right]+n$$

那么我们做一个$g(n)$的前缀和就得到了$f(n)$。现在原式化简为了

$$F(n)=\sum_{k=1}^nk^2f\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$$

直接计算可以做到$O(n+T\sqrt{n})$的复杂度，但不够快。

第二部分

我们考虑计算$F(i),i\in[1,n]$。考虑枚举$k$，然后枚举$n$，计算$k^2f\left(\left\lfloor\dfrac{n}{k}\right\rfloor\right)$对哪些$F(i)$有贡献。对于$\left\lfloor\dfrac{n}{k}\right\rfloor$相同的贡献，显然有贡献的是一段长度为$k$的区间（在末端长度小于等于$k$）。因此差分一下，把区间加转化为单点加。然后做完后前缀和回来即可。

预处理的时间是调和级数。因此总复杂度$O(n\ln n+T)$。

代码