莫比乌斯反演 学习笔记

模板及讲解

整数分块

求 $\sum_{i=1}^n \lfloor \frac ni \rfloor$。

显然可以暴力$O(n)$求。但是这里可以$O(\sqrt n)$ 求。

结论:对于所有的 $\lfloor \frac ni \rfloor$ 都是一段连续的块,并且块的端点可以被枚举。假设当前在 $i$ 处,那么 $\lfloor \frac ni \rfloor$的最后一个值在$\lfloor \frac{n}{\lfloor \frac ni \rfloor} \rfloor$

证明:设$\lfloor \frac ni \rfloor = \lfloor \frac n{i’} \rfloor=k$,并且$i’$为最大的位置。
设$i+d=i’$,$n=ik+p,n=(i+d)k+p’$
可得$p’=p-dk$,则$d_{max}= \lfloor \frac pk \rfloor$
那么$i’=i+d_{max}​$
$$
=i+\lfloor \frac pk \rfloor=i+\lfloor \frac {n\%i}{\lfloor \frac ni \rfloor} \rfloor=\lfloor i+ \frac {n\%i}{\lfloor \frac ni \rfloor} \rfloor=\lfloor \frac {i \cdot \lfloor \frac ni \rfloor}{\lfloor \frac ni \rfloor}+ \frac {n\%i}{\lfloor \frac ni \rfloor} \rfloor \rfloor
$$

$$
= \lfloor \frac {i \cdot \lfloor \frac ni \rfloor+n-\lfloor \frac ni \rfloor \cdot i}{\lfloor \frac ni \rfloor} \rfloor= \lfloor \frac {n}{\lfloor \frac ni \rfloor} \rfloor
$$

得证。
易得$\lfloor \frac ni \rfloor$取值不超过$2\sqrt n$ 个,所以复杂度为$O(\sqrt n)$。

例题:Bzoj 1968

1
2
3
4
5
6
LL l = 1, r, ans = 0ll;
while (l <= n) {
r = (n / (n / l));
ans += (r - l + 1ll) * (n / l);
l = r + 1ll;
}

Bzoj 1257

给出 $n, k$,求$\sum_{i=1}^n k \mod i$

$k \mod i= k -i \cdot \lfloor \frac ki \rfloor$,则$\sum_{i=1}^n k \mod i= \sum_{i=1}^n k -i \cdot \lfloor \frac ki \rfloor=nk-\sum^{n}_{i=1} i \cdot \lfloor \frac ki \rfloor$

发现右边是整除分块的形式,所以加一个等差数列求和公式计算即可。注意此题要判断一下$n,k$的大小。复杂度$O(\sqrt n)$

1
2
3
4
5
6
7
8
LL ans = 0ll, l = 1, r;
if (n > k) ans += (n - k) * k, n = k;
ans += n * k;
while (l <= n) {
r = min(n, (k / (k / l)));
ans -= (l + r) * (r - l + 1ll) / 2ll * (k / l);
l = r + 1ll;
}

此题有升级版,Blog,$T(T \leq 10^6)$组询问$n(n \leq 10^6)$。此时用整除分块会炸。考虑$i \cdot \lfloor \frac ki \rfloor$的意义就是因数和。所以线性筛因数和即可。预处理前缀和后$O(1)$ 处理询问。

线性筛积性函数

线性筛积性函数考虑两个
第一个是$f(p), p$为质数是的取值怎么$O(1)$算
第二个是$f(p^x), p$为质数是的取值怎么$O(1)$算,也就是说我们需要从$f(p^x)$转到$f(p^{x+1})$怎么求

第一个:在某数为质数时需要$O(1)$算出函数值
第二个:线性筛是用最小质因数去筛数,所以对于被筛的数在$p|i$时只需要考虑$f(p^x)$转到$f(p^{x+1})$怎么求
而$gcd(i,p)=1$时利用积性函数性质进行求解即可。

莫比乌斯函数

若 $i=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$,那么有莫比乌斯函数

$$
\mu(i)=
\begin{cases}
1&,i=1 \\
(-1)^k&,\forall a_k=1 \\
0&,\exists a_k\gt1
\end{cases}
$$

性质

1、莫比乌斯函数是积性函数

$μ(a)μ(b)=μ(ab),a⊥b$

运用此性质可以线性筛莫比乌斯函数。

2

$$
\sum_{d\mid n}\mu(d) = [n = 1]​
$$

证明:(二项式定理)

设$n$有$k$种因子。则

$$
\sum_{d\mid n}\mu(d)=\sum_{i=0}^kC^i_k(-1)^i1^{k-r}=[n=1]
$$

线性筛莫比乌斯函数

时间复杂度 $ O(n) $。
有更优秀的杜教筛。

1
2
3
4
5
6
7
8
9
10
11
mu[1] = 1, vis[1] = 1; // mu[1] = 1
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1; // 奇数个 mu[i] = -1
for (int j = 1; j <= tot && (LL)i * (LL)pri[j] <= (LL)n; ++j) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) {
mu[i * pri[j]] = 0; // 一个质因子多个 mu[i] = 0
break;
} else mu[i * pri[j]] = -mu[i]; // 积性函数
}
}

莫比乌斯反演

定义

$F(n)$和$f(n)$是定义在非负整数集合上的两个函数

1、当$$F(n)=\sum_{d|n}f(d)$$

那么有(第一类)莫比乌斯反演

$$
f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})
$$

2、当$F(i)=\sum^{\frac ni}_{d=1}f(d \cdot i)$

那么有(第二类)莫比乌斯反演

$$
f(i)=\sum_{d=1}^{\frac ni}F(d \cdot i)\mu(d)
$$

证明

第一类:
$$
\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{i|\frac{n}{d}}f(i)=\sum_{i|n}f(i)\sum_{d|\frac{n}{i}}\mu(d)=f(n)
$$

证明都是用将 $\mu(k)$ 提后然后根据性质1判断。

变形

欧拉函数变形

$$
\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]=\sum_{i=1}^n\sum_{k\mid i,k\mid n}\mu(k)=\sum_{k\mid n}\mu(k)\lfloor\frac nk\rfloor
$$

运用

求 $gcd = k$ 的个数

例题:Bzoj 2301
题意:询问$(a, b, c, d, k)​$, 求
$$
\sum_{i=a}^{b} \sum_{j=c}^{d} [gcd(i,j)=k]
$$

(下面默认$n \leq m$, 不满足则交换)
解:
我们可以将答案分成几个部分求解,然后$ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)$
依题意设出$f(k)$为$gcd(i,j)=k$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
但是这个并不好求,看见两个求和符号,我们可以想到用莫比乌斯反演来求解。
显然用变形后的两个式子,我们就可以设$g(k)$为$k|gcd(i,j)$的个数$(1 \leq i \leq n, 1 \leq j \leq n)$
$g(k)$非常好算,$g(k)=\lfloor \frac n{k} \rfloor \lfloor \frac m{k} \rfloor$
而显然$g(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} f(ki)$
那么可以莫比乌斯反演
$$
f(k)=\sum_{d=1}^{\lfloor \frac nk \rfloor} \mu(d) \lfloor \frac n{kd} \rfloor \lfloor \frac m{kd} \rfloor
$$
换元$\lfloor \frac nk \rfloor$,整除分块即可。

注意有$n,m$的整除分块是取两者最小值,复杂度也是有保证的。

求 $gcd(i,j)^k$ 的和

例题:BZOJ 4407
题意:
给定$n,m,k$,求
$$
\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^k \mod (10^9+7)
$$

按照套路反演以后得到

$$
\sum_{d=1}^n d^k \sum_{i=1}^{\lfloor \frac nd \rfloor} \mu(i) \lfloor \frac n{di} \rfloor \lfloor \frac m{di}\rfloor
$$

此时我们发现可以分块套分块达到复杂度$O(n)$单次询问。
但是还是不够,那么继续变形

设$T=di$,则

$$
\sum_{i=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|n} d^k \mu(\frac Td)
$$

设$f(T)=\sum_{d|T}d^k \mu(\frac Td)$,发现$d^k$和$\mu(k)$都是积性函数,所以乘积也是积性函数,所以我们可以线性筛$O(n)$算这个积性函数值。

如何线性筛?
线性筛积性函数考虑两个
第一个是$f(p), p$为质数是的取值怎么$O(1)$算
第二个是$f(p^x), p$为质数是的取值怎么$O(1)$算,也就是说我们需要从$f(p^x)$转到$f(p^{x+1})$怎么求

考虑将$T$质因数分解,那么对于每个$p_i$

$$
f(p_i^{x_i})=\sum_{d|p_i^{x_i}}d^k\mu(\frac{p_i^{x_i}}d)
$$

因为有$\mu$的存在,只需要考虑$d=p_i^{x_i}$和$d=p_i^{x_i-1}$的情况,则原式化为

$$
f(p_i^{x_i})=\mu(p_i) \cdot p_i^{k(x_i-1)} + \mu(1) \cdot p_i^{x_ik}
$$

$$
f(p_i^{x_i}) = p_i^{x_ik} - p_i^{k(x_i-1)}
$$

$$
f(p_i^{x_i}) = p_i^{k(x_i-1)}(p_i^k-1)
$$

这个式子可以方便解决$f(p^x), p$为质数是的取值

对于第一个,$f(p)=\mu(1) \cdot p_k + \mu(p) \cdot 1^k=p_k-1$

那么这样就可以线筛了。

莫比乌斯反演一般是
1、两个求和符号
2、用反演公式设出与所求的那个函数符合的函数,然后导出基本式子
3、用技巧(换元、内层外移、观察、莫比乌斯函数容斥性等)来化简式子
4、最后的答案整除分块,必要时将与外层枚举变量无关的式子证明是积性函数线性筛无法证明则打表验证,重点关注质数,质数的幂的值

常见题型

------ 本文结束 ------