数论学习笔记

发表于 2025-10-15 更新于 2025-12-07 分类于 Algorithm 阅读次数：本文字数： 5.4k

上海区域赛，THU 出题，多学一些数学，尤其是各种筛。

狄利克雷卷积

定义

数论函数：定义在正整数集合上的函数。

积性函数：一个数论函数 $f$ 被称为积性函数，满足对于互素的 $x,y$，满足 $f(x)f(y) = f(xy)$。

先定义一些常用的数论函数的符号：

单位函数 $\varepsilon(n) = \begin{cases}1,n = 1\\0,\text{otherwise} \end{cases}$

幂函数 $\text{Id}_k(n) = n^k$，当 $k = 1$ 时为恒等函数 $\text{Id}(n)$，当 $k = 1$ 时为常数函数 $1(n)$。

除数函数 $\sigma_k(n) = \sum_{d\mid n} d^k$，当 $k = 1$ 时为因数和函数 $\sigma(n)$，当 $k = 0$ 时为因数个数函数 $\sigma_0(n)$

欧拉函数 $\varphi(n) = \sum_{i = 1}^{n-1}\limits[(i, n) = 1]$。

莫比乌斯函数 $\mu(n) = \begin{cases}1,n = 1\\0,n \text{有平方因子}\\(-1)^k,n\text{是 k 个不同因数的乘积}\end{cases}$

狄利克雷卷积是定义在数论函数上的一种二元运算，$(f*g)(n) = \sum_{d\mid n}f(d)g(\dfrac{n}{d})$。

常见性质

若 $f,g$ 是积性函数，则 $(f*g)$ 也是积性函数。

除数函数与幂函数

$(f * 1)(n) = \sum_{d\mid n}f(d)1(\dfrac{n}{d}) = \sum_{d\mid n}f(d)$，也就是一个函数与常数函数做狄利克雷卷积，就变成了 $n$ 的因数的函数和。

因此 $(\text{Id}_k * 1) = \sum_{d\mid n}d^k = \sigma_k$

欧拉函数与恒等函数

这里回忆一下欧拉定理与欧拉函数相关结论：

$\varphi(p^k) = p^k - p^{k-1}$，因为在 $[1, p^k]$ 中，只有 $p,p^2,...,p^k$ 整除 $p^k$。

若 $m=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$，则 $\varphi(m)=m\prod_{i=1}^k(1-\dfrac{1}{p_i})$。

然后就是幂函数与恒等函数的经典结论：欧拉函数与常数函数卷积等于恒等函数。

这样，我们可以把 $x$ 写成 $\sum_{d\mid x}\varphi(d)$ ，然后枚举除数用于推导式子。

$(\varphi * 1)(n) = \sum_{d\mid n}\varphi(d) = \text{Id}(n)$，即 $(\varphi * 1) = \text{Id}$。

因为若 $n = p^m$，$\sum_{d\mid n}\varphi(d) = \varphi(1) + \sum_{i=1}^m\varphi(p^i) = 1 + \sum_{i=1}^m(p^i - p^{i - 1}) = p^m = n$。

那么将 $n$ 分解为 $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$，根据积性函数的性质即可得到 $(\varphi * 1)(\prod p^m) = \prod(\varphi * 1)(p^m) = \prod p^m = n$。

交换律

$(f * g)(n) = (g * f)(n)$

结合律

$((f * g) * h)(n) = (f * (g * h))(n)$

对函数加法的分配律

$(f * (g + h))(n) = (f * g)(n) + (f * h)(n)$

单位元

单位函数 $\varepsilon$ 是狄利克雷卷积的单位元。

逆元

$f$ 存在狄利克雷逆元的必要条件是 $f(1)\ne 0$。

莫比乌斯反演

莫比乌斯函数是常数函数 $1$ 的狄利克雷逆元，记为 $\mu$，即 $(1 * \mu) = \sum_{d\mid n}\mu(d) = \varepsilon$。

莫比乌斯函数被应用于下面的莫比乌斯反演公式：

$g(n) = \sum_{d\mid n} f(d) \iff f(n) = \sum_{d\mid n}\mu(d)g(\dfrac{n}{d})$。用狄利克雷卷积的形式就是 $(f * 1) = g\iff f = g * \mu$。

主要是用来推导式子，最常见的是利用 $(1 * \mu) = \varepsilon$ ，来把和式转化成含有莫比乌斯函数的式子，然后枚举除数，配合分块处理。

例： \[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1] &=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i,j)}\mu(d) \\ &=\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i,\,d\mid j}\mu(d) \\ &=\sum_{d=1}^n \mu(d)\,\Big\lfloor \dfrac{n}{d}\Big\rfloor \Big\lfloor \dfrac{m}{d}\Big\rfloor \end{aligned} \]

线性筛

线性筛的核心是，让每个数都只被它的最小质因子标记，这样就是 $O(n)$ 的。因此，我们筛素数的同时也会得到每个数的最小质因子。

重点是用筛法求各类积性函数。

// minp(x) 可以找到 x 大于 1 的最小质因子
std::vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

筛法求欧拉函数

设 $p_1$ 是 $n$ 的最小质因子，且 $n = p_1\times n^\prime$，根据欧拉定理 $\varphi(n) = n\prod\dfrac{p-1}{p}$，讨论 $n^\prime$ 与 $p_1$ 的关系：

若 $n^\prime \equiv 0\pmod {p_1}$，说明 $n^\prime$ 包含了 $p_1$ 质因子，因此 $\varphi(n) = \varphi(n^\prime)\times p_1$。
否则，说明 $n^\prime$ 不含 $p_1$，此时 $\varphi(n) = \varphi(n^\prime)\times (p_1 - 1)$。

筛法求莫比乌斯函数

设 $p_1$ 是 $n$ 的最小质因子，且 $n = p_1\times n^\prime$，讨论 $n^\prime$ 与 $p_1$ 的关系：

首先，$\mu(1) = 1$。
若 $n$ 是素数，$\mu(n) = 1$
若 $n^\prime \equiv 0\pmod {p_1}$，说明 $n$ 有平方因子，$\mu(n) = 0$
否则，$\mu(n) = -\mu(n^\prime)$

筛法求约数个数函数

用 $d_i$ 表示约数个数，$num_i$ 表示 $i$ 的最小质因子出现次数。

约数个数定理：若 $n = \prod_{i=1}^mp_i^{c_i}$，那么 $d_i = \prod_{i=1}^m(c_i + 1)$，根据乘法原理。

原理：

当 $i$ 为素数时，$num_i = 1,d_i = 2$。同时，设 $q = $，其中 $p$ 为 $i$ 的最小质因子。
当 $p$ 为 $q$ 的质因子时，$num_i = num_q + 1$，$d_i = \dfrac{d_q}{num_i} \times (num_i + 1)$。
当 $p,q$ 互素时，$num_i = 1,d_i = d_q\times (num_i + 1)$。

筛法求因数和函数

用 $\sigma_i$ 表示因数和，$num_i$ 表示 $i$ 的最小质因子出现次数，$sum_i$ 表示当前最小质因子部分的和。

约数和定理：若 $n = \prod_{i=1}^mp_i^{c_i}$，那么 $\sigma(n) = \prod_{i=1}^m(1 + p_i + p_i^2 + ... + p_i^{c_i}) = \displaystyle\prod_{i=1}^m\dfrac{p_i^{c_i+1}-1}{p_i-1}$。

原理：

当 $i$ 是素数时，$num_i = 1, \sigma_i = i + 1,sum_i = i + 1$。同时，设 $q = $，其中 $p$ 为 $i$ 的最小质因子。
当 $p$ 为 $q$ 的质因子时，$num_i = num_q + 1, sum_i = sum_q + p^{num_i},\sigma_i = \sigma_{q}\times \dfrac{sum_i}{sum_{q}}$。
当 $p,q$ 互素时，$num_i = 1, sum_i = 1 + p, \sigma_i = \sigma_{q} \times (1 + p)$。

通过这样的思路，还可以计算一般的积性函数 $f$。

O(值域) 预处理的 O(1) 查询 GCD

不讲具体证明，只讲原理：

定理一：可以将值域中的每个 $x$ 分解成 $\{a,b,c\}$ 三个数之积，满足 $a,b,c\le \sqrt x$ 或为素数，定义这种分解为合法分解。

定理二：将 $x$ 分解为 $a\times b\times c$，令 $a_0 = (a, y), a_1 = (b,\dfrac{y}{a_0}),a_2=(c,\dfrac{y}{a_0a_1})$，则有 $(x, y) = a_0\times a_1\times a_2$。

那么我们再考虑如何分解和查询。

分解：对于 $x\ge 2$，找到 $x$ 的最小质因子 $p$，以及 $\dfrac{x}{p}$ 的合法分解 $a\times b\times c$，那么 $x$ 的一种分解即为 $\{ap, b, c\}$ 的升序排列。并且可以证明，一定有，我们可以跑一次线性筛，预处理一个 $\sqrt n\times \sqrt n$ 的 gcd 数组。

查询：由于我们预处理了一个 gcd 数组，求 $(n, m)$ 时，将 $n$ 分解为 $a\times b\times c$，每次求 $t = a/b/c$，将最终结果乘上 $t$ 并将 $m$ 除以 $t$。具体地，若此时考虑的数 $x$ 为素数，求 $(x, m)$ 是简单的，否则必有 $x\le \sqrt{n}$，且 $(x,m) = (x, m\bmod x)$，因此只需要预处理出 $\sqrt V$ 内任意两个数的 gcd 后即可 $O(1)$ 查询。

BSGS/exBSGS

大步小步算法（Baby Step Giant Step, BSGS）是一种用来求解离散对数问题（即模意义下对数）的算法，即给出 $a^x\equiv b\pmod m$ 中 $a,b,m$ 的值（需要保证 $a,m$ 互素）求解 $x$。而 exBSGS 可以在 $a,m$ 不互素的情况下计算。

若 $a,m$ 互素，根据欧拉定理，$a^{\varphi(m)} = 1\pmod m$，朴素求解的复杂度是 $O(m)$。

我们设 $x = At - B$，则原式化为 $a^{At-B} \equiv b\pmod m$，即 $a^{At}\equiv ba^{B}\pmod m$，我们预处理出右侧所有可能的取值，再固定一个 $t$ 计算出左边所有可能的取值，如果发现某个值在右边出现过，此时 $At-B$ 就是我们要求的 $x$。

$B$ 可能的取值有 $\varphi(m) \bmod t$ 个，$A$ 可能的取值有 $\lfloor\dfrac{\varphi(m)}{t}\rfloor$ 个，因此取 $t = \sqrt{\varphi(m)}$ 是最好的。时间复杂度 $O(\sqrt m)$。

而如果 $a,m$ 不互素，尝试转化到 $a,m$ 互素的情形。

当 $x > 0$ 时，$a^x\equiv b\pmod m$ 等价于 $a^{x-1}a + nm = b$，设 $d = (a, m)$，那么 $\dfrac{a^{x-1}a}{d} + \dfrac{nm}{d} = \dfrac{b}{d}$，即 $\dfrac{a}{d}a^{x-1} \equiv \dfrac{b}{d}\pmod {\dfrac{m}{d}}$，此时如果 $(a,\dfrac{m}{d}) = 1$，就可以用 BSGS 了，否则可以继续递归下去，直到互素。

但是这样算出来不一定是最小解，还需要枚举。

\[\sum_{x=1}^{\lfloor \frac{R}{d} \rfloor}\mu(x)(\lfloor \frac{R}{dx}\rfloor-\lfloor\frac{L-1}{dx}\rfloor)^n\]