常见积性函数

列出一些后面可能会用到的常见积性函数。

常数函数：$1(n)=1$.

单位元：$\epsilon(n)=[n=1]$.

恒等函数：$\operatorname{id}(n)=n$.

因数个数：$d(n)=\sum\limits_{i\mid n}^n 1$.

因数和：$\sigma(n)=\sum\limits_{i\mid n}^n i$.

欧拉函数：$\varphi(n)=\sum\limits_{i=1}^n [\gcd(i, n)=1]$.

莫比乌斯函数

莫比乌斯函数

狄利克雷卷积

对于两个数论函数 $f, g$，其狄利克雷卷积记为 $t=f\ast g$，则：

单位元：$\epsilon(n) = \begin{cases} 1,&n=1\\ 0,&n> 1\end{cases}$，满足 $e\ast t=t$.

常用性质

因此 $1\ast \mu = \epsilon$.

常用推导技巧

技巧 $1$

技巧 $2$

其中 $\tau(x)$ 可以是任意积性函数。

这可以理解为枚举因数：把枚举 $i$ 变成了枚举 $i^{\prime}=i\times x$，因此函数括号内值要改变，$\sum$ 的上界也要改变。

整除分块

整除分块，又称数论分块，可以快速计算合写含有除法向下取整的和式。

常见的和式形式为：$\sum_{i=1}^n f(i)g(\left\lfloor\frac{n}{i}\right\rfloor)$.

一般情况下，若 $g(x)$ 可以 $\mathcal{O}(1)$ 计算，且 $f_i$ 的区间和可以 $\mathcal{O}(1)$ 计算，则和式可在 $\mathcal{O}(\sqrt{n})$ 的时间复杂度被算出。

引理 $1$

证明：

根据取整的定义 $\Rightarrow \frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r$.

代入可证：

引理 $2$

对于给定整数 $n$，若 $i$ 固定，则满足 $\left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{j}\right\rfloor$ 的 $j$，最大值为 $\left\lfloor\dfrac n{\lfloor\frac {n}{i}\rfloor}\right\rfloor$.

一般思路

由引理二，对任意 $i\in [l, \left\lfloor\frac n{\lfloor\frac {n}{l}\rfloor}\right\rfloor]$ ，$\left\lfloor\frac{n}{i}\right\rfloor$ 都相等。

将它们归为一块，同时计算，容易发现，最多有 $\sqrt{n}$ 个块。

例 $1$

求和式 $\sum_{i=1}^n f(i)\left\lfloor\frac{n}{i}\right\rfloor$.

先计算出 $f(i)$ 的前缀和 $s(i)=\sum_{j=1}^i f(i)$，之后按照一般思路，把 $[l, \left\lfloor\frac n{\lfloor\frac {n}{l}\rfloor}\right\rfloor]$ 归为一块，每块分别计算。

参考代码：

for(int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += (s[r] - s[l - 1]) * (n / l);
}

例 $2$

求和式 $\sum\limits_{d=1}^{\mathrm{min}(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}f(d)
\lfloor\frac{f(n)}{d}\rfloor\lfloor\frac{f(m)}{d}\rfloor$.

二维数论分块，设 $s(i)=\sum_{j=1}^i f(i)$.

将代码中 r = n / (n / i) 替换成 r = min(n / (n / i), m / (m / i)) 即可。

for(int l = 1, r; l <= min(n, m); l = r + 1) {
    r = min(n / (n / l), m / (m / l));
    ans += (f[r] - f[l - 1]) * g[n / l] * g[m / l];
}

P3327 [SDOI2015]约数个数和

利用整除分块，可以在 $\mathcal{O}(n\sqrt{n})$ 内预处理出 $g(n)=\sum\limits_{i=1}^{n}\lfloor\frac{n}{i}\rfloor$，则：

再次整除分块即可，于是以 $\mathcal{O}(n\sqrt n + T\sqrt n)$ 的时间复杂度求出了答案。

P1829 [国家集训队]Crash的数字表格

前面两个 $\sum$ 只需预处理 $\mu(x)$ 的前缀和，最后两个 $\sum$ 可以用等差数列 $\mathcal{O}(1)$ 算出，于是答案可线性计算。

整除分块，复杂度为 $\sum\limits_{i=1}^n \sqrt\frac{n}{i}$，计算可知，当 $n=10^7$ 时，左边式子的值 $<2\times 10^7$，可以通过。

注意取模、逆元。

for(int d = 1; d <= min(n, m); d++) {
    int t = min(n / d, m / d), tmp = 0;
    for(int l = 1, r; l <= t; l = r + 1) {
        r = min((n / d) / ((n / d) / l), (m / d) / ((m / d) / l));
        (tmp += (mu[r] - mu[l - 1]) % mod * g(n / d / l, m / d / l) % mod) %= mod;
    }
    ans = (ans + tmp * d % mod) % mod;
}

P3312 [SDOI2014]数表

先忽略 $a$ 的限制？

这样虽然形式简单，但并不能继续进行…

换成下面的形式：

记 $t=dx$，则可以更改枚举顺序，继续简化：

观察推导过程，可知当 $\sigma(d)\leq a$ 时才会对答案有贡献。

设 $g(t)=\sum_{d\mid t} \sigma(d) \mu(\frac{t}{d})$.

以 $a$ 为关键字，从小到大枚举询问。$a$ 变大时，有一些 $g(t)$ 的值需要增加，可以直接枚举新加入的数的所有倍数，来找到所有被贡献的 $t$.

用树状数组维护 $g(t)$，时间复杂度为 $\mathcal{O}(q\sqrt n\log n+n\log^2 n)$.

P3455 [POI2007]ZAP-Queries

P3172 [CQOI2015]选数

杜教筛、整除分块。

P6810 「MCOI-02」Convex Hull 凸包

对于 $\sum\limits_{x=1}^{\min(n, m)}\tau(x)
\sum\limits_{d=1}^{\lfloor\frac{\min(n, m)}{x}\rfloor}\mu(d)$，暴力循环枚举即可。复杂度用调和级数算，是 $\mathcal{O}(n\ln n)$.

对于 $\sum\limits_{i=1}^{\lfloor\frac{n}{xd}\rfloor}\tau(xid)
\sum\limits_{j=1}^{\lfloor\frac{m}{xd}\rfloor}\tau(xjd)$，可以在预处理后 $\mathcal{O}(1)$ 计算。

先线性筛出所有的 $\tau(x)$，预处理出 $s(x,y)=\sum\limits_{i=1}^{y} \tau(xi)$.

若 $x$ 固定，则 $y\in[1, \lfloor\frac{\min(n, m)}{x}\rfloor]$，所以预处理的复杂度也是 $\mathcal{O}(n\ln n)$ 级别的。

这tm会被卡常。

所以有更简单的推导方法：

预处理出 $\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} \tau(id)$ 即可。

P3704 [SDOI2017]数字表格

其中：

继续：

常见套路，设 $t=dx$，则：

设 $g_t=\prod_{d\mid t} {f_d}^{\mu (t/d)}$，则：

枚举每个 $d$，预处理出 $g_t$ 数组，复杂度为调和级数 $\frac{n}{1}+\frac{n}{2}+\cdots+\frac{n}{n}=n\ln n$.

多测，对每次询问，利用数论分块计算 $\operatorname{Ans}$，需要先算出 $g_t$ 的前缀积。

时间复杂度为 $\mathcal{O}(t\sqrt n+n\ln n)$.

注意：代码取模时，指数部分要 $\bmod (p-1)$ 而不是 $\bmod p$，由费马小定理知 $a^{p-1} \equiv a^0\pmod p$.

P2257 YY的GCD

设 $t=px$，