前置芝士1——数论分块
UVA11526 H(n)
P2261 [CQOI2007]余数求和
P2260 [清华集训2012]模积和
P3935 Calculating
前置芝士2——线性筛
P2158 [SDOI2008]仪仗队
SP526 DIV - Divisors
P4626 一道水题 II
SP22461 SMALL - Smallest Number
CF1017F The Neutral Zone论如何选择筛法
以及你的算法优化技巧与数学能力
P6810 「MCOI-02」Convex Hull 凸包
P5495 Dirichlet 前缀和
P6788 「EZEC-3」四月樱花
莫比乌斯反演
就是把一个看起来只能暴力算的柿子化成一个可以一下子算出来或者数论分块可以算出来的东西
以下都默认 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
LCMSUM - LCM Sum（2倍经验）
loj LCMSUM（3倍经验）
P2398 GCD SUM
P1390 公约数的和（2倍经验）
SP21615 NAJPWG - Playing with GCD
SP3871 GCDEX - GCD Extreme
AT5310 [ABC162E] Sum of gcd of Tuples (Hard)（难度绿？？？我大不服
莫反加整除分块
P3455 [POI2007]ZAP-Queries
P2522 [HAOI2011]Problem b
SP26017 GCDMAT - GCD OF MATRIX
SP26045 GCDMAT2 - GCD OF MATRIX (hard)（卡常，慎入！！
VLATTICE - Visible Lattice Points
杜教筛
主要思路就是构造一个积形函数$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)