Peter的莫比乌斯反演与各种筛法题单
题单介绍
### 前置芝士1——[数论分块](https://oi-wiki.net/math/mobius/#_3)
[UVA11526 H(n)](https://www.luogu.com.cn/problem/UVA11526)
[P2261 [CQOI2007]余数求和](https://www.luogu.com.cn/problem/P2261)
[P2260 [清华集训2012]模积和](https://www.luogu.com.cn/problem/P2260)
[P3935 Calculating](https://www.luogu.com.cn/problem/P3935)
### 前置芝士2——[线性筛](https://oi-wiki.net/math/sieve/)
[P2158 [SDOI2008]仪仗队](https://www.luogu.com.cn/problem/P2158)
[SP526 DIV - Divisors](https://www.luogu.com.cn/problem/SP526)
[P4626 一道水题 II](https://www.luogu.com.cn/problem/P4626)
[SP22461 SMALL - Smallest Number](https://www.luogu.com.cn/problem/SP22461)
[CF1017F The Neutral Zone论如何选择筛法](https://www.luogu.com.cn/problem/CF1017F)
### 以及你的算法优化技巧与数学能力
[P6810 「MCOI-02」Convex Hull 凸包](https://www.luogu.com.cn/problem/P6810)
[P5495 Dirichlet 前缀和](https://www.luogu.com.cn/problem/P5495)
[P6788 「EZEC-3」四月樱花](https://www.luogu.com.cn/problem/P6788)
### [莫比乌斯反演](https://oi-wiki.net/math/mobius)
就是把一个看起来只能暴力算的柿子化成一个可以一下子算出来或者数论分块可以算出来的东西
以下都默认 $n\le m$
#### 形式1
$$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{x|j}\mu(x)$$
$$=\sum_{x=1}^n\mu(x)\sum_{i=1}^n\sum_{j=1}^m[x|i][x|j]$$
$$=\sum_{x=1}^n\mu(x)\lfloor {n\over x}\rfloor\lfloor {m\over x}\rfloor$$
数论分块即可 $O(n)$ 预处理， $O(\sqrt n)$ 单次询问
#### 形式2
$$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{x|j}\phi(x)$$
$$=\sum_{x=1}^n\phi(x)\sum_{i=1}^n\sum_{j=1}^m[x|i][x|j]$$
$$=\sum_{x=1}^n\phi(x)\lfloor {n\over x}\rfloor\lfloor {m\over x}\rfloor$$
数论分块即可 $O(n)$ 预处理， $O(\sqrt n)$ 单次询问
#### 形式3
$$\sum_{i=1}^n\sum_{j=1}^mf(\gcd(i,j))=\sum_{d=1}^nf(d)\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]$$
$$=\sum_{d=1}^nf(d)\sum_{i=1}^{\lfloor{n\over d}\rfloor}\sum_{j=1}^{\lfloor{m\over d}\rfloor}[\gcd(i,j)=1]$$
$$=\sum_{d=1}^nf(d)\sum_{k=1}^{\lfloor{n\over d}\rfloor}\mu(k)\lfloor {n\over dk}\rfloor\lfloor {m\over dk}\rfloor$$
然后是一个重要的思路，令$dk=T$
$$=\sum_{T=1}^n\lfloor {n\over T}\rfloor\lfloor {m\over T}\rfloor\sum_{d|T}f(d)\mu({T\over d})$$
数论分块即可 $O(n)$ 预处理， $O(\sqrt n)$单次询问
莫比乌斯反演形式千千万，要多做才能做出感觉来。
#### 莫比乌斯反演优化多次/单次询问
[疯狂 LCM](https://www.luogu.com.cn/problem/P1891)
[LCMSUM - LCM Sum（2倍经验）](https://www.luogu.com.cn/problem/SP5971)
[loj LCMSUM（3倍经验）](https://loj.ac/p/6375)
[P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398)
[P1390 公约数的和（2倍经验）](https://www.luogu.com.cn/problem/P1390)
[SP21615 NAJPWG - Playing with GCD](https://www.luogu.com.cn/problem/SP21615)
[SP3871 GCDEX - GCD Extreme](https://www.luogu.com.cn/problem/SP3871)
[AT5310 [ABC162E] Sum of gcd of Tuples (Hard)（难度绿？？？我大不服](https://www.luogu.com.cn/problem/AT5310)
#### 莫反加整除分块
[P3455 [POI2007]ZAP-Queries](https://www.luogu.com.cn/problem/P3455)
[P2522 [HAOI2011]Problem b](https://www.luogu.com.cn/problem/P2522)
[SP26017 GCDMAT - GCD OF MATRIX](https://www.luogu.com.cn/problem/SP26017)
[SP26045 GCDMAT2 - GCD OF MATRIX (hard)（卡常，慎入！！](https://www.luogu.com.cn/problem/SP26045)
[VLATTICE - Visible Lattice Points](https://www.luogu.com.cn/problem/SP7001)
### [杜教筛](https://oi-wiki.net/math/du/)
$\sum_{i=1}^nf(i),f$ 为积形函数
主要思路就是构造一个积形函数$g$，使得它本身前缀和与
$$\sum_{i=1}^n\sum_{d|i}f(d)g(\frac{i}{d})$$
好算一点
那么我们有
$$\sum_{i=1}^n\sum_{d|i}f(d)g(\frac{i}{d})=\sum_{d=1}^ng(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}f(k)$$
$$g(1)\sum_{k=1}^nf(k)=\sum_{i=1}^n\sum_{d|i}f(d)g(\frac{i}{d})-\sum_{d=2}^ng(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}f(k)$$
递归计算即可，当然可以预处理，具体见wiki写的
### [Min25筛](https://oi-wiki.net/math/min-25/)
学会这个就能搞定一切积形函数前缀和了
题单放不下了我就放在这里
[P1835 素数密度（请小题大做）](https://www.luogu.com.cn/problem/P1835)
[P5493 质数前缀统计（min25前置芝士）](https://www.luogu.com.cn/problem/P5493)
[P5325 【模板】Min_25筛（板子）](https://www.luogu.com.cn/problem/P5325)
[SP20173 DIVCNT2 - Counting Divisors (square)（1倍经验）](https://www.luogu.com.cn/problem/SP20173)
[SP20174 DIVCNT3 - Counting Divisors (cube)（2倍经验）](https://www.luogu.com.cn/problem/SP20174)
[SP34096 DIVCNTK - Counting Divisors (general)（3倍经验）](https://www.luogu.com.cn/problem/SP34096)
[SP19975 APS2 - Amazing Prime Sequence (hard)（有技巧的min25，需要熟练了解其精髓）](https://www.luogu.com.cn/problem/SP19975)
[SP22549 DIVFACT4 - Divisors of factorial (extreme)（用min25处理中间问题）](https://www.luogu.com.cn/problem/SP22549)
### 欧拉计划分区（可能要翻墙
[中文翻译](https://pe-cn.github.io/problems/)
[欧拉计划388](https://projecteuler.net/problem=388)
[欧拉计划625](https://projecteuler.net/problem=625)