莫比乌斯反演 & 狄利克雷卷积

基础知识

莫比乌斯函数

$$
\mu(n)=
\begin{cases}
1&n=1\\
0&n\text{ 含有平方因子}\\
(-1)^k&k\text{ 为 }n\text{ 的本质不同质因子个数}\ \end{cases}
$$

狄利克雷卷积:对于两个数论函数 $f, g$,其狄利克雷卷积为 $t=f\ast g$,则:

$$
t(n)=\sum_{i\times j=n} f(i)g(j)
$$

单位元:$\epsilon(n) = \begin{cases} 1,&n=1\\ 0,&n> 1\end{cases}$,满足 $e\ast t=t$.

性质

$$
\sum_{d|n}\mu(d)=\epsilon(n)=\begin{cases} 1,&n=1\\ 0,&n> 1\end{cases}
$$

因此 $1\ast \mu = \epsilon$.

常用推导技巧1

$$
[\gcd(i, j)=1]=\sum_{d\mid \gcd(i, j)}\mu(d)
$$

常用推导技巧2

$$
\sum_{i=1}^{n}\sum_{j=1}^{m}\tau(i)\tau(j)[\gcd(i, j)=x]=
\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}
\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\tau(xi)\tau(xj)[\gcd(i, j)=1]\\
$$

其中 $\tau(x)$ 可以是任意积性函数。

这可以理解为:把枚举 $i$ 变成了枚举 $i^{\prime}=i\times x$,因此函数括号内的值要改变,$\sum$ 的上界也要改变。

P3327 [SDOI2015]约数个数和

$$
\begin{aligned}
\operatorname{Ans}
&= \sum_{i=1}^n\sum_{j=1}^m d(ij)\\
&= \sum_{i=1}^n\sum_{j=1}^m \sum_{p\mid i}\sum_{q\mid j}[\gcd(p, q)=1]\\
&= \sum_{p=1}^n\sum_{q=1}^m\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{q}\rfloor[\gcd(p, q)=1]\\
&= \sum_{p=1}^n\sum_{q=1}^m\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{q}\rfloor\sum_{d\mid \gcd(p,q)}\mu(d)\\
&= \sum_{d=1}^{\mathrm{min}(n, m)}\mu(d)\sum_{p=1}^n\sum_{q=1}^m\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{q}\rfloor[p\mid d][q\mid d]\\
&= \sum_{d=1}^{\mathrm{min}(n, m)}\mu(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{q=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\lfloor\frac{n}{p}\rfloor\lfloor\frac{m}{q}\rfloor\\
&= \sum_{d=1}^{\mathrm{min}(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{q=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dq}\rfloor\\
&= \sum_{d=1}^{\mathrm{min}(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dp}\rfloor\sum_{q=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{dq}\rfloor
\end{aligned}
$$

利用整除分块,可以在 $\mathcal{O}(n\sqrt{n})$ 内预处理出 $g(n)=\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$,则:

$$
\begin{aligned}
\operatorname{Ans}
&= \sum_{d=1}^{\mathrm{min}(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(d)\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{dp}\rfloor\sum_{q=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{dq}\rfloor\\
&= \sum_{d=1}^{\mathrm{min}(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(d)
\lfloor\frac{g(n)}{d}\rfloor\lfloor\frac{g(m)}{d}\rfloor
\end{aligned}
$$

整除分块即可,于是以 $\mathcal{O}(n\sqrt n + T\sqrt n)$ 的时间复杂度求出了答案。

P1829 [国家集训队]Crash的数字表格

$$
\begin{aligned}
\operatorname{Ans}
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{lcm}(i, j)\\
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{\operatorname{gcd}(i, j)}\\
&=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m\frac{i\times j}{d} [\gcd(i,j)=d]\\
&=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\frac{(i\cdot d)\times (j\cdot d)}{d} [\gcd(i,j)=1]\\
&=\sum_{d=1}^{\min(n,m)}d\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j[\gcd(i,j)=1]\\
&=\sum_{d=1}^{\min(n,m)}d\cdot\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j\sum_{x\mid \gcd(i, j)}\mu(x)\\
&=\sum_{d=1}^{\min(n,m)}d\sum_{x=1}^{\min(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(x)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}(i\times j)[x\mid i][x\mid j]\\
&=\sum_{d=1}^{\min(n,m)}d\sum_{x=1}^{\min(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(x)\cdot x^2\sum_{i=1}^{\lfloor\frac{n}{dx}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dx}\rfloor}(i\times j)
\end{aligned}
$$

前面两个 $\sum$ 只需预处理 $\mu(x)$ 的前缀和,最后两个 $\sum$ 可以用等差数列 $\mathcal{O}(1)$ 算出,于是答案可线性计算。

$$
\begin{aligned}
g(n,m) &= \sum_{i=1}^n\sum_{j=1}^mi\times j\\
&=\frac{n(n+1)}{2}\frac{m(m+1)}{2}
\end{aligned}
$$

整除分块,复杂度为 $\sum\limits_{i=1}^n \sqrt\frac{n}{i}$,计算可知,当 $n=10^7$ 时,左边式子的值 $<2\times 10^7$,可以通过。

注意取模、逆元。

for(int d = 1; d <= min(n, m); d++) {
    int t = min(n / d, m / d), tmp = 0;
    for(int l = 1, r; l <= t; l = r + 1) {
        r = min((n / d) / ((n / d) / l), (m / d) / ((m / d) / l));
        (tmp += (mu[r] - mu[l - 1]) % mod * g(n / d / l, m / d / l) % mod) %= mod;
    }
    ans = (ans + tmp * d % mod) % mod;
}

P3312 [SDOI2014]数表

$$
\begin{aligned}
\operatorname{Ans}
&= \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x=1}^{\min(n, m)}x[x\mid i][x\mid j]\\
&= \sum_{x=1}^{\min(n, m)}x\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{x}\rfloor\\
\end{aligned}
$$

没做完

P3455 [POI2007]ZAP-Queries

$$
\sum_{i=1}^{a}\sum_{j=1}^{b}[\gcd(i, j) = d]\\
\sum_{i=1}^{a/d}\sum_{j=1}^{b/d} [\gcd(i, j) = 1]\\
\sum_{i=1}^{a/d}\sum_{j=1}^{b/d}\sum_{d\in \gcd(i, j)}\mu(d)\\
\sum_{i=1}^{a/d}\sum_{j=1}^{b/d}\sum_{x=1}^{\min(a/d,b/d)} \mu(x)[d\mid i][d\mid j]\\
\sum_{x=1}^{\min(a/d, b/d)}\mu(x)\sum_{i=1}^{a/d}[d\mid i]\sum_{j=1}^{b/d}[d\mid j]\\
\sum_{x=1}^{\min(a/d, b/d)}\mu(x)\lfloor\frac{a}{xd}\rfloor\lfloor\frac{b}{xd}\rfloor
$$

P3172 [CQOI2015]选数

$$
\begin{aligned}
\operatorname{Ans}
&= \sum_{a_1=L}^{h}\sum_{a_2=L}^{h}\cdots\sum_{a_n=L}^{h}[\gcd(a_1,a_2\cdots, a_n)=k]\\
&= \sum_{a_1=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\sum_{a_2=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\cdots\sum_{a_n=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}[\gcd(a_1,a_2\cdots a_n)=1]\\
&= \sum_{a_1=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\sum_{a_2=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\cdots\sum_{a_n=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\sum_{d\mid \gcd(a_1,a_2\cdots a_n)}\mu (d)\\
&= \sum_{a_1=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\sum_{a_2=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\cdots\sum_{a_n=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}\cdot \sum_{d=1}^{\lfloor\frac{h}{k}\rfloor}\mu (d)[d\mid a_1][d\mid a_2]\cdots [d\mid a_n]\\
&= \sum_{d=1}^{\lfloor\frac{h}{k}\rfloor}\mu (d)\cdot \sum_{a_1=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}[d\mid a_1]\cdot \sum_{a_2=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}[d\mid a_2]\cdots\sum_{a_n=\lceil\frac{l}{k}\rceil}^{\lfloor\frac{h}{k}\rfloor}[d\mid a_n]\\
&= \sum_{d=1}^{\lfloor\frac{h}{k}\rfloor}\mu (d)\cdot \sum_{a_1=\lfloor\frac{l-1}{k}\rfloor+1}^{\lfloor\frac{h}{k}\rfloor}[d\mid a_1]\cdot \sum_{a_2=\lfloor\frac{l-1}{k}\rfloor+1}^{\lfloor\frac{h}{k}\rfloor}[d\mid a_2]\cdots\sum_{a_n=\lfloor\frac{l-1}{k}\rfloor+1}^{\lfloor\frac{h}{k}\rfloor}[d\mid a_n]\\
&= \sum_{d=1}^{\lfloor\frac{h}{k}\rfloor}\mu (d)\cdot (\lfloor\frac{h}{kd}\rfloor – \lfloor\frac{l-1}{kd}\rfloor)^n
\end{aligned}
$$

杜教筛、整除分块。

P6810 「MCOI-02」Convex Hull 凸包

$$
\begin{aligned}
\operatorname{Ans}
&= \sum_{i=1}^{n}\sum_{j=1}^{m}\tau(i)\tau(j)\tau(\gcd(i, j))\\
&= \sum_{x=1}^{\min(n, m)}\tau(x)
\sum_{i=1}^{n}\sum_{j=1}^{m}\tau(i)\tau(j)[\gcd(i, j)=x]\\
&= \sum_{x=1}^{\min(n, m)}\tau(x)
\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}
\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\tau(xi)\tau(xj)[\gcd(i, j)=1]\\
&= \sum_{x=1}^{\min(n, m)}\tau(x)
\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}
\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\tau(xi)\tau(xj)
\sum_{d\mid \gcd(i,j)}\mu(d)\\
&= \sum_{x=1}^{\min(n, m)}\tau(x)
\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}
\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\tau(xi)\tau(xj)
\sum_{d=1}^{\lfloor\frac{\min(n, m)}{x}\rfloor}\mu(d)[d\mid i][d\mid j]\\
&= \sum_{x=1}^{\min(n, m)}\tau(x)
\sum_{d=1}^{\lfloor\frac{\min(n, m)}{x}\rfloor}\mu(d)
\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}[d\mid i]\tau(xi)
\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}[d\mid j]\tau(xj)\\
&= \sum_{x=1}^{\min(n, m)}\tau(x)
\sum_{d=1}^{\lfloor\frac{\min(n, m)}{x}\rfloor}\mu(d)
\sum_{i=1}^{\lfloor\frac{n}{xd}\rfloor}\tau(xid)
\sum_{j=1}^{\lfloor\frac{m}{xd}\rfloor}\tau(xjd)
%&= \sum_{x=1}^{\min(n, m)}\tau^3(x)
% \sum_{d=1}^{\lfloor\frac{\min(n, m)}{x}\rfloor}\mu(d)\tau^2(d)
% \sum_{i=1}^{\lfloor\frac{n}{xd}\rfloor}\tau(i)
% \sum_{j=1}^{\lfloor\frac{m}{xd}\rfloor}\tau(j)\\
\end{aligned}
$$

对于 $\sum\limits_{x=1}^{\min(n, m)}\tau(x)
\sum\limits_{d=1}^{\lfloor\frac{\min(n, m)}{x}\rfloor}\mu(d)$,暴力循环枚举即可。复杂度用调和级数算,是 $\mathcal{O}(n\ln n)$.

对于 $\sum\limits_{i=1}^{\lfloor\frac{n}{xd}\rfloor}\tau(xid)
\sum\limits_{j=1}^{\lfloor\frac{m}{xd}\rfloor}\tau(xjd)$,可以在预处理后 $\mathcal{O}(1)$ 计算。

先线性筛出所有的 $\tau(x)$,预处理出 $s(x,y)=\sum\limits_{i=1}^{y} \tau(xi)$.

若 $x$ 固定,则 $y\in[1, \lfloor\frac{\min(n, m)}{x}\rfloor]$,所以预处理的复杂度也是 $\mathcal{O}(n\ln n)$ 级别的。

这tm会被卡常。

所以有更简单的推导方法:

$$
\begin{aligned}
\operatorname{Ans}
&= \sum_{i=1}^{n}\sum_{j=1}^{m}\tau(i)\tau(j)\tau(\gcd(i,j))\\
&= \sum_{i=1}^{n}\sum_{j=1}^{m}\tau(i)\tau(j)\sum_{d\mid \gcd(i,j)}1\\
&= \sum_{d=1}^{n}\cdot \sum_{i=1}^{n}[d\mid i]\tau(i)\cdot\sum_{j=1}^{n}[d\mid j]\tau(j)\\
&= \sum_{d=1}^{n}\cdot \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \tau(id)\cdot \sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} \tau(jd)
\end{aligned}
$$

预处理出 $\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \tau(id)$ 即可。

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();