数论分块
对于形如
\[\sum_{i=1}^nf(i)g(\lfloor\frac{n}{i}\rfloor) \]的式子，我们可以发现 \(\lfloor\dfrac{n}{i}\rfloor\) 的值可以分成若干块，具体的，设上一块的右边界为 \(r'\)，则当前块的左边界 \(l=r'+1\)，右边界 \(r=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor\)。块数为 \(O(\sqrt n)\) 量级。
code:
LL S(LL n) {
LL s = 0;
for (LL l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
s += (SumF(r) - SumF(l - 1)) * G(n / l);
}
return s;
}
扩展：
多维数论分块
如果式子形如
\[\sum_{i=1}^nf(i)g(\lfloor\frac{a_1}{i}\rfloor,\lfloor\frac{a_2}{i}\rfloor,\cdots,\lfloor\frac{a_k}{i}\rfloor) \]在取总块右边界的时候把 \(k\) 个块的右边界取 \(\min\) 即可。块的量级为 \(O(k\sqrt{a})\)。
LL S(LL n) {
LL s = 0;
for (LL l = 1, r; l <= n; l = r + 1) {
r = INT64_MAX;
for (int i = 1; i <= k; ++i) {
r = min(r, a[i] / (a[i] / l));
}
s += (SumF(r) - SumF(l - 1)) * G(a[1] / l, a[2] / l, ..., a[k] / l);
}
return s;
}
多维嵌套数论分块
式子形如
\[\begin{aligned} S_k(n)&=\sum_{i=1}^ng_k(i)S_{k-1}(\lfloor\frac{n}{i}\rfloor)\\ S_0(n)&=f(n) \end{aligned} \]直接递归，总块数量级为 \(O(n^{1-2^{-k}})\)。
LL S(LL n, int k) {
if (k == 0) {
return F(n);
}
LL s = 0;
for (LL l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
s += (SumG(r, k) - SumG(l - 1, k)) * S(n / l, k - 1);
}
return s;
}
积性函数
定义
如果一个数论函数 \(f(n)\) 满足对于所有 \(\gcd(i,j)=1\)，有 \(f(ij)=f(i)f(j)\)，那么 \(f(n)\) 被称为积性函数。
特别的，如果对于所有 \(i,j\) 都有 \(f(ij)=f(i)f(j)\)，那么 \(f(n)\) 被称为完全积性函数。
性质
如果 \(f(n)\) 和 \(g(n)\) 都是积性函数，那么下列函数也是积性函数：
\[\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f(x)^p\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g(x/d) \end{aligned} \]常见积性函数
- 单位函数 \(\epsilon(n)=[n=1]\)，完全积性函数。
- 幂函数 \(\operatorname{id}^k(n)=n^k\)，\(\operatorname{id}^1\) 一般简记为 \(\operatorname{id}\)，完全积性函数。
- 常数函数 \(1(n)=1\)，也记作 \(I\)，完全积性函数。
- 因数个数函数 \(\operatorname{d}(n)=\displaystyle\sum_{d\mid n}1=\displaystyle\sum_{d=1}^n[d\mid n]\)。
- 除数函数 \(\sigma_k(n)=\displaystyle\sum_{d\mid n}d^k\)，\(k=1\) 时为因数和函数，\(k=0\) 时为因数个数函数。
- 欧拉函数 \(\varphi(n)=\displaystyle\sum_{i=1}^n[\gcd(i,n)=1]\)。
- 莫比乌斯函数 \(\mu(n)\)，设 \(n=\prod_{i=1}^kp_i^{e_i}\)，那么有 \(\mu(n)=\begin{cases} 1 & \text{if } n=1\\ 0 & \text{if } e_i>1\\ (-1)^k & \text{otherwise.} \end{cases}\)。