整除分块
复杂度保证：
（来自oiwiki
重要结论：
对于 \(\left \lfloor \frac{n}{a} \right \rfloor = \left \lfloor \frac{n}{b} \right \rfloor\) 成立的最大的 \(b\) 为 $\left \lfloor \frac{n}{\left \lfloor \frac{n}{a} \right \rfloor} \right \rfloor $ 。
对于答案 \(\sum_{i=1}^{n}f(i)g(\left \lfloor \frac{n}{i} \right \rfloor)\)
设 \(r = \left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor\) ，\(s(i) = \sum_{i=1}^n f(i)\) ；
区间 \([l, r]\) 的贡献即为 $(s(r) - s(l-1)) \times g(\left \lfloor \frac{n}{l} \right \rfloor) $
数论函数
积性函数：满足对于 \(gcd(a,b)=1\) 的 \(a, b\) 有 \(f(ab)=f(a)f(b)\) 的数论函数。
完全积性函数：满足 \(\forall a, b, f(ab)=f(a)f(b)\) 的数论函数
常见数论函数（都是积性函数）：
-
设 \(n = \prod_{i=1}^c p_i^{k_i}\)
-
\(\epsilon(n) = [n=1]\) （完全）
-
\(1(n)=1\) （完全）
-
\(Id(n) = n\) （完全）
-
\(d(n) = \sum_{d|n}1=\prod_{i=1}^c(k_i+1)\)
-
\(\sigma(n) = \sum_{d|n}d\)
-
\(\varphi(n)=\sum_{i=1}^n[gcd(i, n) = 1]= n \times \prod_{i=1}^c\frac{p_i-1}{p_i}\)
-
\(\mu(n)=[max_{i=1}^c k_i \le 1](-1)^c\)
对于一个积性函数，求 \(f(n)\) 需要知道所有的 \(f(p_i^{k_i})\) ；
对于一个完全积性函数，求 \(f(n)\) 需要知道所有的 \(f(p_i)\) ；
数论卷积
定义两个数论函数 \(f(n), g(n)\) 的卷积为 \(h(n) = \sum_{d|n}f(d)g(\frac{n}{d})\) ，记作 \(h = f * g\) 。
-
\(\epsilon * f = f\)
-
\(1 * 1 = d\)
-
\(1 * Id = \sigma\)
-
\(1 * \varphi = Id\)
-
\(1 * \mu = \epsilon\)
莫比乌斯反演
若 \(g(n)=\sum_{d|n}f(d)\) ，则有 \(f(n) = \sum_{d|n}\mu(\frac{n}d)g(d)\)
\(g = 1 * f \Rightarrow g * \mu = (1 * \mu) * f \Rightarrow f * \epsilon = g * \mu \Rightarrow f = g * \mu\)
-
莫反拆gcd
经典应用，\(f(n)\) 灵活使用 ，套用数论卷积 / 前缀和预处理 / 调和级数因数预处理，多测一次 / 二次整除分块
\[\sum_{i=1}^{n}\sum_{j=1}^{n} f(gcd(i, j)) \]\[= \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nf(d)[gcd(i,j)=d] \]\[=\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}d\right\rfloor}f(d)[gcd(i,j)=1] \]\[=\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}d\right\rfloor}f(d) \sum_{k|gcd(i,j)}\mu(k) \]\[=\sum_{d=1}^n\sum_{k=1}^{\left\lfloor\frac{n}d\right\rfloor} \mu(k) \sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor} \sum_{j=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}f(d) \]\[=\sum_{d=1}^n\sum_{k=1}^{\left\lfloor\frac{n}d\right\rfloor} \mu(k)f(d) \left\lfloor\frac{n}{dk}\right\rfloor^2 \]\[=\sum_{T=1}^n\sum_{d|T}f(d)\mu(\frac{T}d) \left\lfloor\frac{n}T\right\rfloor^2 \]
Ex：