莫比乌斯反演

· · 个人记录

数论函数

数论函数指定义域为正整数集，值域是整数集的函数

积性函数和完全积性函数

对于一个数论函数f，当gcd(a,b)=1时，f(ab)=f(a)f(b)，则称其为积性函数

对于一个数论函数f，若 f(ab)=f(a)f(b)，则称其为完全积性函数

莫比乌斯函数

\mu(n) = \begin{cases} 1 \qquad &n=1 \\ (-1)^k \qquad &n=\prod\limits_{i=1}^{k} p_i \\ 0 \qquad &\text{otherwise} \end{cases}

莫比乌斯函数是积性函数

狄利克雷卷积

h(n)=\sum_{d \mid n}f(d)g(\frac{n}{d})

满足结合律，交换律

存在单位元f \times \epsilon= f，\epsilon(n)=[n=1]=\begin{cases}1&n=1\\0&n\ne1\end{cases}

存在逆元，对于每个f(1)\ne 0的函数f，都存在函数g，使得f\times g= \epsilon

一些卷积的结论

\varphi \times 1=id μ \times id=\varphi μ \times 1=\epsilon \epsilon \times1 =1

莫比乌斯反演

f=g \times 1\iff g=f \times μ

证明：

f=f \times \epsilon=f \times \mu \times 1=g \times 1 \iff g=f \times μ

数论分块

若要求\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor，可以用数论分块实现O(\sqrt n)计算

code: 
for(int l=1,r;l<=n;l=r+1)
    r=n/(n/l),ans+=(r-l+1)*(n/l);

ZAP-Queries：求\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=k]\ (n \leqslant m)

&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=k] \\ =&\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[gcd(i,j)=1] \\ =&\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\epsilon(gcd(i,j)) \\ =&\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d \mid i \wedge d \mid j}\mu(d)\\ =&\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d) \sum_{i=1 \wedge d \mid i}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1 \wedge d \mid j}^{\lfloor \frac{m}{k} \rfloor}1\\ =&\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d) (\sum_{i=1 \wedge d \mid i}^{\lfloor \frac{n}{k} \rfloor}1)(\sum_{j=1 \wedge d \mid j}^{\lfloor \frac{m}{k} \rfloor}1)\\ =&\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}\mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \end{aligned}

约数个数和：求\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij)\ (n \leqslant m)

&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij) \\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j} [\gcd(x,y)=1] \\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j}\epsilon(gcd(x,y)) \\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j}\sum_{d \mid x \wedge d \mid y}\mu(d) \\ =&\sum_{d=1}^n\mu(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x\mid i}\sum\limits_{y\mid j}[d \mid x \wedge d \mid y]\\ =&\sum_{d=1}^n\mu(d)\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{y=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dy}\rfloor\\ =&\sum_{d=1}^n\mu(d)\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor\frac{n}{dx}\rfloor\sum_{y=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor\frac{m}{dy}\rfloor\\ =&\sum_{d=1}^n\mu(d)f(\lfloor\frac{n}{d}\rfloor)f(\lfloor\frac{m}{d}\rfloor)\\ &f(n)=\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor \end{aligned}

Crash的数字表格 / JZPTAB：求\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)\ (n \leqslant m)

\begin{aligned} &\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j) \\ =&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{ij}{gcd(i,j)} \\ =&\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{ij}{d}[gcd(i,j)=d] \\ =&\sum\limits_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{k \mid i \wedge k \mid j}\mu(k)ijd \\ =&\sum\limits_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)ij[k \mid i \wedge k \mid j] \\ =&\sum\limits_{d=1}^{n}d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i[k \mid i]\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}j[k \mid j] \\ =&\sum\limits_{d=1}^{n}d\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)k^2\sum_{i=1}^{\lfloor \frac{n}{kd} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{kd} \rfloor}j \\ =&\sum\limits_{d=1}^{n}df(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor) \\ &f(n,m)=\sum_{k=1}^{n}\mu(k)k^2\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}j \\ \end{aligned}

数字表格：求\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f(gcd(i,j))\ (n \leqslant m)，其中f为斐波那契数列

\begin{aligned} &\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{m}f(gcd(i,j) \ \\ =&\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=d]} \ \\ =&\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}[gcd(i,j)=1]} \ \\ =&\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum\limits_{k \mid i \wedge k \mid j}\mu(k)} \ \\ =&\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}[k \mid i \wedge k \mid j]} \ \\ =&\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor} \ \\ =&\prod\limits_{d=1}^{n}\prod\limits_{k=1}^{\lfloor \frac{n}{d} \rfloor}f(d)^{\mu(k)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor} \ \\ =&\prod\limits_{T=1}^{n}\left(\prod\limits_{d \mid T}f(d)^{\mu(\frac{T}{d})}\right)^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor} \ \\ \end{aligned}