当前位置：首页 > news >正文

数论 I.exe

news 2026/7/17 15:16:37

0x00 前言

仅个人纪录，无参考价值（）。

感谢 OI-WIKI 与 deepseek 老师的支持（）。

0x01 扩展欧几里得算法 / exgcd

exgcd 常用于解决形如关于 \(x, y\) 的 \(ax + by = \gcd (a, b)\) 的二元一次不定方程，其中 \(a, x, b, y\) 都为非负整数。

0x01.1 推导

让我们回到一般的 gcd，每一步我们根据 \(\gcd (a, b) = \gcd (b, a \bmod b)\) 来缩小范围。

如果 \(b = 0\) 时，\(a = \gcd (a, b)\)，此时 \(x = 1, y = 0\)。
我们设 \(bx + (a \bmod b)y = \gcd (a, b)\) 的解为 \(x_0, y_0\)，也就是下一步 \(\gcd (b, a \bmod b)\) 的解。
\(bx_0 + (a \bmod b)y_0 = \gcd (a, b) = ax + by\)
由于 \((a \bmod b) = a - (\lfloor \dfrac{a}{b} \rfloor \times b)\)，简化为 \(bx_0 + [a - (\lfloor \dfrac{a}{b} \rfloor \times b)]y_0 = ax + by\)
\(bx_0 + ay_0 - (\lfloor \dfrac{a}{b} \rfloor \times b)y_0 = ax + by\)
\(ay_0 + b(x_0 - \lfloor \dfrac{a}{b} \rfloor y_0) = ax + by\)

所以，我们得到了 \(x = y_0, y = x_0 - \lfloor \dfrac{a}{b} \rfloor y_0\)，代码如下。

::::info[Code]

pair <int, int> exgcd (int a, int b) {if (b == 0) return make_pair (1, 0);int x, y; tie (x, y) = exgcd (b, a % b);return make_pair (y, x - a / b * y);
}

::::

0x01.2 拓展

那么 \(ax + by = c\) 的问题呢？

由裴蜀定理可得 \(\gcd (a, b) \mid ax + by\)，那么必定有 \(\gcd (a, b) \mid c\)，否则此方程无整数解。

由于 \(\gcd (a, b) \mid c\)，所以 \(\dfrac{c}{\gcd (a, b)}\) 必定为整数。我们将 \(ax + by = \gcd (a, b)\) 求解出来之后，可以在两边同时乘一个 \(\dfrac{c}{\gcd (a, b)}\) 就可以得到 \(ax + by = c\) 的整数解了。

不仅如此，我们可以由 \(a(x + kb) + b(y - ka) = c, k \in \mathbf{Z}\) 得到此方程的通解，但最小的周期不一定是 \(kb\) 与 \(ka\)，我们只需要求出最小周期就可以了。

不难发现，最小的只能有 \(a(x + k \dfrac{b}{\gcd (a, b)}) + b(y - k \dfrac{a}{\gcd (a, b))}) = c\) 得到 \(k \dfrac{b}{\gcd (a, b)}\) 与 \((-k) \dfrac{a}{\gcd (a, b))}\)。

若令 \(ax_0 + by_0 = \gcd (a, b)\)，\(ax + by = c\) 的通解为：

\[\begin{cases} x = x_0 + k \dfrac{b}{\gcd (a, b)}, \\ y = y_0 - k \dfrac{a}{\gcd (a, b)}, \end{cases} k \in \mathbf{Z} \]

exgcd 通常与其它算法一起结合，由于其推导与辗转相除法有关，所以称它为扩展欧几里得算法。

0x02 扩展中国剩余定理 / excrt

你说的对，但是为什么不讲中国剩余定理？

因为这次是真扩展（）

crt / excrt 常用于解决关于 \(x\) 的一次同余方程问题，形如

\[\begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ x \equiv a_k \pmod {m_k} \end{cases} \]

求 \(x\) 的一个解。

0x02.1 推导

考虑每两个方程之间的关联，也就是

\[\begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \end{cases} \]

可以推出 \(a_1 + pm_1 = x = a_2 + qm_2\)，
\(pm_1 - qm_2 = a_2 - a_1\)，
可以发现这个形如 \(ax + by = c\)，可以用 exgcd 解出 \(p, q\)，
最后，我们可以得到 \(x \equiv m_1p + a_1 \pmod {\operatorname{lcm}(m_1, m_2)}\)。
我们发现这个形式也形如一个同余方程，所以不断将两两方程合并即可。

::::info[code]

pair <int, int> excrt (int a1, int m1, int a2, int m2) {int G = gcd (m1, m2);// 记得用裴蜀定理判无解！！！！！ if ((a2 - a1) % G != 0) return make_pair (-1, -1);// 这里详见 1.2 int p, q;tie (p, q) = exgcd (m1 / G, m2 / G); p = p * (a2 - a1) / G;int rmod = lcm (m1, m2);return make_pair ((m1 * p + a1) % rmod, rmod);
}

::::

0x02.2 拓展

excrt 还可以用来拆分一些复杂的模问题。

例 0. 古代猪文 (部分)

假设我们现在在模数很小的情况下，可以在合理复杂度内通过此题。但现在我们要求解 \(x \bmod 999911658\) 的值，如何求解？

我们发现 \(999911658\) 并不是一个质数，考虑将它质因数分解，\(999911658 = 2 \times 3 \times 4679 \times 35617\)，可以用 excrt 将它转化为

\[\begin{cases} x \equiv a1 \pmod 2 \\ x \equiv a2 \pmod 3 \\ x \equiv a3 \pmod {4679} \\ x \equiv a4 \pmod {35617} \end{cases} \]

然后直接求解。

0x03 Lucas / exLucas

你说得对，但是有没有古代猪文更完整一点版？

有的，兄弟，有的。

0x03.1 Lucas

作者太菜了，暂时还不会证明 \ll。

我们约定 \(n \lt k\) 时，\(\dbinom{n}{k} = 0\)，你只需要记住这样一个东西：

\(\dbinom{n}{k} \equiv \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{k}{p} \rfloor} \times \dbinom{n \bmod p}{k \bmod p} \pmod p\)，当且仅当 \(p\) 是质数。

不难发现，在 \(p\) 是很小的质数模数的时候，通过预处理后面的那一坨可以达到 \(O(p + \log_pn)\) 的。

上面我们说的模数很小的算法就是 Lucas。

0x03.2 exLucas

你说得对，但是 \(p\) 不为质数呢？

令 \(P = p\)、\(\dbinom{n}{m} = x\)，我们首先将 \(P\) 质因数分解为 \(p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}\)，那么用 excrt 可以得到

\[\begin{cases} x \equiv x_1 \pmod {p_1^{a_1}} \\ x \equiv x_2 \pmod {p_2^{a_2}} \\ \ \ \ \ \ \ \ \ \ \vdots \\ x \equiv x_k \pmod {p_k^{a_k}} \end{cases} \]

也就是我们只需要得到 \(x \bmod {p_i^{a_i}}\) 就可以直接求解 \(x\)。

考虑回到组合数的定义 \(\dfrac{n!}{m!(n-m)!} \bmod p^i\)，这些阶乘很烦，如果是这样的形式就好了 \(\dfrac{\frac{n!}{p^x}}{\frac{m!}{p^y}\frac{(n-m)!}{p^z}} \times p^{x-y-z} \pmod {p^i}\)

也就是 \(n!, m!, (n - m)!\) 分别把带 \(p\) 的因子去掉，我们将它归类到一类问题：如何求 \(n! \bmod p\) 与 \(n!\) 中 \(p\) 的因子个数。

\(n! = 1 \times 2 \times 3 \times \cdots \times n\)，我们将 \(p\) 的倍数提出来，
\(n! = (p \times 2p \times \cdots) \times 1 \times 2 \times \cdots\)
除去 \(p\) 之后，发现这玩意又是一个重复：\(n! = p^{\lfloor \frac{n}{p} \rfloor}(1 \times 2 \times \cdots) \times 1 \times 2 \times \cdots = p^{\lfloor \frac{n}{p} \rfloor}{\lfloor \dfrac{n}{p} \rfloor}! \times \cdots\)
别忘了这玩意实在模 \(p^i\) 意义下的，所以后面那玩意其实是有循环节的。
\(n! = p^{\lfloor \frac{n}{p} \rfloor}{\lfloor \dfrac{n}{p} \rfloor}! \times [1 \times 2 \times 3 \cdots \times (p^i - 1)]^{\lfloor \frac{n}{p^i} \rfloor} \times [1 \times 2 \times \cdots \times (n \bmod p^i )]\)
前面的是一层递推，后面的可以 \(O(p^i)\) 处理，复杂度大概就是 \(O(P \log_p n)\)。
n! 的 \(p\) 因子个数咋求？
hyw，你都推导出来 \(n! = p^{\lfloor \frac{n}{p} \rfloor}{\lfloor \dfrac{n}{p} \rfloor}! \times \cdots\) 了，后面那一坨是没有 \(p\) 的，你还不会递归吗？

::::info[Code]

int f (int n, int p, int pk) {if (n == 0) return 1;int ret1 = 1, ret2 = 1;// 循坏节 1, 2 for (int i = 1; i <= pk; ++i) if (i % p) ret1 = ret1 * i % pk; // 这里别忘判 i % p != 0 了 ret1 = fstpow (ret1, n / pk, pk);for (int i = pk * (n / pk); i <= n; ++i) if (i % p) ret2 = i % pk * ret2 % pk; // 这里别忘判 i % p != 0 了 return f (n / p, p, pk) * ret1 % pk * ret2 % pk;
}
int g (int n, int p) {if (n < p) return 0;return (n / p) + g (n / p, p);
}

::::

好了，exLucas 的核心部分没了，相信剩下的你都会了（）

0x04 BSGS / exBSGS

BSGS 求解类似于 \(a^x \equiv b \pmod m\) 的问题。

0x04.1 BSGS

我们考虑 \(\gcd (a, m) = 1\) 时，也就是 \(a\) 在模 \(m\) 意义下有逆元。

考虑一点暴力的：分块，设块长为 \(B\)，每个 \(a^x \equiv b \pmod m\) 可以写成 \(a^{pB-q} \equiv b \pmod m\)，也就是 \(a^{pB} \equiv ba^q \pmod m\)。

我们发现 \(a^q\) 可以 \(O(B)\) 预处理，枚举 \(a^{pB}\) 也是 \(O(\lceil\dfrac{m}{B}\rceil)\) 的，那么取 \(B = \lceil \sqrt{m} \rceil\) 时有最佳复杂度 \(\Theta(\lceil \sqrt{m} \rceil)\)，当然前提是用哈希写，用 map 存的话要多只 \(\log\)。

::::info[Code]

unordered_map <int, int> mp;
int bsgs (int a, int b, int mod) {mp.clear ();a %= mod; b %= mod;if (mod == 1) return 0;if (b == 1) return 0;if (a == 0) return b == 0 ? 1 : -1;int len = sqrt (mod) + 1;for (int i = 0; i < len; ++i) mp[b * fst (a, i, mod) % mod] = i;a = fst (a, len, mod);for (int i = 1; i <= len; ++i) {int val = fst (a, i, mod);int tmp = -1;if (mp.count (val)) tmp = mp[val];if (tmp >= 0 && i * len - tmp >= 0) return i * len - tmp;}return -1;
}

::::

0x04.2 exBSGS

你说的对，但是 \(\gcd (a, m) \neq 1\) 呢？

好好好，那么我们考虑把 \(\gcd (a, m)\) 强行凑成 \(1\)。

\(a^x \equiv b \pmod m\) 考虑两边同时除 \(d_1 = \gcd (a, m)\)，如果 \(d_1 \nmid b\)，则原方程无解，否则可以变成 \(\dfrac{a}{d_1} \times a^{x - 1} \equiv \dfrac{b}{d_1} \pmod {\dfrac{m}{d_1}}\)
如果 \(\gcd (\dfrac{a}{d_1}, \dfrac{m}{d_1}) \neq 1\)，那么继续 \(d_2 = \gcd(\dfrac{a}{d_1}, \dfrac{m}{d_1})\)，判无解变成 \(\dfrac{a^2}{d_1d_2} \times a^{x-2} \equiv \dfrac{b}{d_1d_2} \pmod {\dfrac{m}{d_1d_2}}\)
继续这样，一直到 \(\gcd (a, m) = 1\)，令 \(D = d_1d_2 \cdots d_k\)，方程变为了 \(\dfrac{a^k}{D} \times a^{x-k} \equiv \dfrac{b}{D} \pmod {\dfrac{m}{D}}\)，此时 \(a\) 就有逆元了，我们将 \(x - k\) 用 BSGS 求解出来即可。

由于模板题判的东西有点多，不放代码了。

0x05 数论函数

0x05.1 函数章

0x05.1.1 莫比乌斯函数 \(\mu\)

\(\mu\) 的定义如下。

\[\mu (x) = \begin{cases} 1, \ \ \ \ \ \ \ \ x = 1 \\ 0, \ \ \ \ \ \ \ \exists p \in Prime, p^2 \mid x \\ (-1)^k, \text{otherwise}\end{cases} \]

其中，我们令 \(n = \prod _{i=1} ^k {p_i^{a_i}}\)，\(k\) 即为定义中的 \(k\)。也就是说，一个数如果有两个相同的质因子，它的 \(\mu\) 值即为 \(0\)。

一些性质

性质 1. \(\mu (x)\) 是积性函数，但不是完全积性函数。

由定义可得若 \(p\) 是一个质数，\(\mu (p) = -1\)，\(k \ge 2\) 时，\(\mu (p^k) = 0\)。

假设 \(x = \prod p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\)。若有一个 \(a_i \ge 2\)，那么必定有 \(\mu (p_i^{a_i}) = \mu (x) = 0\)；若没有一个 \(a_i \ge 2\)，则每个 \(\mu (p_i^{a_i}) = -1\)，乘起来刚好是 \(\mu(x) = {(-1)}^k\)。

所以对于任意两个互质的数 \(n, m\)，他们的唯一分解一定不同，进而不会有相同的项，乘起来表示的一定是 \(\mu(n \times m)\)。

性质 2. \(\sum_{d \mid n} \mu (d) = [n = 1]\)。

还是令 \(n = \prod p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\)。注意到 \(d = \prod p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}\)，若存在一个 \(b_i \ge 2\)，那么它对整个和式的贡献为 \(0\)。

所以我们可以直接简化为 \(n' = x = \prod p_1p_2\cdots p_k\)。那么有 \(\sum_{d\mid n}\mu(d) = \sum_{d\mid n'}\mu(d)\)。

我们直接根据定义，枚举一下当前的 \(d\) 选了多少个质数，再结合一下二项式定理有

\[\sum _ {d \mid n'} \mu (d) \\ = \sum _ {i = 0} ^ k \dbinom{k}{i} {(-1)}^i \\ = {(1 + (-1))}^k \\ = [k = 0] \\ = [n = 1] \]

证毕。

0x05.1.2 欧拉函数 \(\varphi\)

\(\varphi (x)\) 表示小于等于 \(x\) 的数中与 \(x\) 互质的数的个数，~~非常简陋的定义~~。

由定义可知，对于一个质数 \(p\)，\(\varphi (p^k) = p^k - p^{k-1}\)。

一些性质

下文都假设 \(x = \prod p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\)。

性质 1. \(\varphi (x) = x \prod _{i=1}^k (1 - \dfrac{1}{p_i})\)

容斥一下，我们先去掉 \(p_i\) 的倍数，再将多减掉的加回来，就是 \(p_ip_j\) 的倍数，以此类推，可以得到

\[\varphi (x) \\ = x - \sum _i \dfrac{n}{p_i} + \sum _{i\lt j} \dfrac{n}{p_ip_j} \cdots \\ = x (1 - \sum \dfrac{1}{p_i} + \sum \dfrac{1}{p_ip_j} \cdots) \\ = x \prod (1 - \dfrac{1}{p_i}) \]

也可以这样理解：

在 \(x\) 个数中不选到 \(p_1\) 的概率为 \((1 - \dfrac{1}{p_1})\)，不选到 \(p_2\) 的概率为 \((1 - \dfrac{1}{p_2})\)，以此类推，没有一个 \(n\) 的质因子的概率为 \(\prod (1 - \dfrac{1}{p_i})\)，再乘 \(x\) 个数即为最终的答案。

性质 2. \(\varphi (x)\) 是积性函数，不是完全积性函数。

\[\prod \varphi(p_i^{a_i}) \\ = \prod p_i^{a_i - 1} (p - 1) \\ = \prod p_i^{a_i} (1 - \dfrac{1}{p_i}) \\ = x \prod (1 - \dfrac{1}{p_i}) \\ = \varphi (n) \]

不难发现只有最初式子中的各个项互质才有这个式子，也就是必须满足 \(\gcd (p_1, p_2) = \gcd (p_2, p_3) = \cdots = 1\)，所以 \(\varphi\) 并不是完全积性函数。

同理可得 \(\varphi\) 也为积性函数，证毕。

性质 3. \(x = \sum _{d \mid n} \varphi (d)\)。

我们考虑 \(n\) 个分数 \(\dfrac{1}{n},\dfrac{2}{n},\dfrac{3}{n},\cdots,\dfrac{n}{n}\)。

现在我们把这些分数约分，最终的形式肯定长这样 \(\dfrac{a}{d}, \gcd (a, d) = 1\)，这其中 \(d\) 一定是 \(n\) 的一个因子。

要想 \(\gcd (a, d) = 1, a \lt d\)， \(a\) 的个数其实就是 \(\varphi (d)\)。当 \(d\) 取完所有 \(n\) 的正因子之后，也就把 \(n\) 个分数取完了。

0x05.1.3 others

这里还有一些位未提到的函数：

\(\epsilon (x) = [n = 1]\)，完全积性。
\(\operatorname{id}_k (x) = x^k\)，\(k = 1\) 时通常省略，完全积性。
\(1 (x) = 1\)，完全积性。
\(\sigma_k (x) = \sum _ {d \mid x} d^k\)，\(k = 0\) 通常记作 \(d (x)\) 或 \(\tau (x)\)，\(k = 1\) 时通常省略，积性。

0x05.2 狄利克雷卷积

0x05.2.1 定义

形如这样的关于两个函数 \(f(x), g(x)\) 的式子称为 \(f(x), g(x)\) 的狄利克雷卷积，写作 \((f * g)(n)\)。

\[(f*g)(n) = \sum _{d \mid n} f(d)g(\dfrac{n}{d}) = \sum _ {dp = n} f(d)g(p) \]

这个东西是数论函数的一个非常重要的运算，证明是一般就用两个东西可以互推，化为和式来证明。

这里给几个性质与非常常见的卷积式子。

0x05.2.2 性质

交换律：\(f * g = g * f\)；
结合律：\((f * g) * h = f * (g * h)\)；
分配律：\((f + g) * h = f * h + g * h\)；
单位元：\(f * \epsilon = \epsilon * f = f\)；

0x05.2.3 一些常见式子

\(\epsilon = \mu * 1 \Longleftrightarrow \sum _ {d \mid n} \mu (d)\)
\(d = 1 * 1\)
\(\sigma = \operatorname{id} * 1\)
\(\varphi = \operatorname{id} * \mu\)

这其中对于第四个式子，可以这样简单的证明一下：

\[\sum _ {d \mid n} \varphi (d) = n \\ \varphi * 1 = \operatorname{id} \\ \varphi * 1 * \mu = \operatorname {id} * \mu \\ \varphi * (1 * \mu) = \operatorname {id} * \mu \\ \varphi * \epsilon = \operatorname {id} * \mu \\ \varphi = \operatorname {id} * \mu \]

还有其他更多的一些式子，需要在实际运用中去发掘。

0x05.3 筛法

筛法本质上是一种用来求解有关质数问题的方法，但正因为质数的特殊性，使得这些筛可以通过一些乘法关系来处理函数关系。

0x05.3.1 质数筛

如果我们要求解这样一个问题：在 \(1\) 到 \(n\) 中，有多少个质数，该怎么办？

显然，判断单个数是否是质数需要 \(O (\sqrt n)\)，若 \(n \ge 10^6\)，这个复杂度就不可接受了。

埃氏筛

我们引入一种新的思路，把每个数的倍数打上标记，打上标记的数肯定不是质数，就像把这些倍数筛出去，剩下的就全是质数了。

::::info[Code]

for (int i = 2; i <= n; ++i) {if (!vis[i]) {prime[++cnt] = i;if (i * i > n) continue;// 这里从 i * i 开始，是因为如果从 i * 2, i * 3, i * 5 ... 开始，它们肯定都被 2, 3, 5 ... 筛过了，所以直接跳过就行了 for (int j = i * i; j <= n; j += i) vis[j] = true;}
}

::::

它的时间复杂度为 \(O(n \log \log n)\)，当然它并不是我们的重点。

线性筛

埃氏筛仍有优化空间，如 \(30 = 2 \times 3 \times 5\)，它不仅会被 \(2\) 筛到，还会被 \(3, 5\) 筛到，重复的标记合数使得复杂度过大。

我们想让每个合数只被筛一次，不妨就用它的最小质因数来筛它。\(20\) 就只会被 \(2\) 筛到。

按照这个思路，我们可以写出如下代码。

::::info[Code]

for (int i = 2; i <= n; ++i) {if (!vis[i]) prime[++cnt] = i;for (int j = 1; j <= cnt && i * prime[j] <= n; ++j) {vis[i * prime[j]] = true;if (i % prime[j] == 0) {// i % prime[j] == 0 说明 i 的因子中已经包含了 prime[j]，如果继续筛下去，prime[j] 就不是 i * prime[j] 的最小质因子了。 break;}}
}

::::

这样，我们便得到了 \(O(n)\) 的筛法。

0x05.3.2 函数筛

线性筛

它不仅仅能筛质数，还因为其独特的“最小质因子”的特殊性质，可以用来求解一些数论函数。

对于 \(f(x)\)，我们只需考虑三种情况：\(x\) 为质数，\(x = i \times p_j\) 的两种，一种 \(\gcd (i, p_j) = 1\)，一种 \(i \mid p_j\)。

\(\mu (x)\)
- 对于 \(x \in Prime\) 时，由定义知 \(\mu (x) = -1\)。
- 对于 \(x = i \times p_j, \gcd (i, p_j) = 1\) 时，\(\mu (x) = -\mu (i)\)。
- 对于 \(x = i \times p_j, i \mid p_j\) 时，\(\mu (x) = 0\)。
\(\varphi (x)\)
- 对于 \(x \in Prime\) 时，由定义知 \(\varphi (x) = x - 1\)。
- 对于 \(x = i \times p_j, \gcd (i, p_j) = 1\) 时，\(\varphi (x) = \varphi (x) \times \varphi (p_j)\)。
- 对于 \(x = i \times p_j, i \mid p_j\) 时，\(\varphi (x) = \varphi (x) \times p_j\)。
\(d (x)\)

这种情况时，我们需要一个辅助数组 \(f (x)\) 表示 \(x\) 的最小质因子次幂加一。
- 对于 \(x \in Prime\) 时，\(d (x) = 2, f (x) = 2\)。
- 对于 \(x = i \times p_j, \gcd (i, p_j) = 1\) 时，\(d (x) = d (i) \times 2, f (x) = 2\)。
- 对于 \(x = i \times p_j, i \mid p_j\) 时，\(d (x) = d (i) + \dfrac {d(i)}{f (i)}, f (x) = f (i) + 1\)。

其他的函数可以自行推导一下，本质上都是一个主函数和一个关于最小质因子的函数结合起来。

杜教筛

从这里开始的筛法都求解这样一类问题：给你一个函数 \(f\)，求它的前缀和 \(F (x) = \sum _{i = 1} ^x f(i)\)。

我们构造 \(f * g = h\)，所以 \(h (n) = \sum _{d \mid n} f (d) g (\frac {n}{d})\)，下文令 \(H (n) = \sum _{i = 1} ^n h(i)\)。

\[H (n) \\ = \sum _{i = 1} ^n h(i) \\ = \sum _{i = 1} ^ n \sum _{d \mid i} f (d) g (\frac{n}{d}) \\ = \sum _ {d = 1} ^ n g (d) \sum _ {i = 1} ^ n f (\frac {i}{d}) [d \mid i] \\ = \sum _ {d = 1} ^ n g (d) \sum _ {i = 1} ^ {\small {\lfloor \frac {n}{d} \rfloor}} f (i) = \sum _{d = 1} ^ n F (\lfloor \frac {n}{d} \rfloor) \]

\(d = 1\) 时，我们有 \(g (1) F (n) = H (n) - \sum _ {d = 2} ^ n g_d F (\lfloor \frac {n}{d} \rfloor)\)。我们构造出了一个关于 \(F\) 的递推关系，前提是快速求出 \(G, H\)。

由于我太菜了，所以这里有一份来自 ds 老师的时间复杂度证明。

一、关键引理（二进制分组放缩）

我们需要证明以下求和估计：

\[\sum_{i=1}^{m} \frac{1}{\sqrt{i}} = O(\sqrt{m}) \]

证明：将区间 \([1, m]\) 按二进制分组：

\[[1,1],\ [2,3],\ [4,7],\ \dots,\ [2^k,\ 2^{k+1}-1] \]

对于区间 \([2^k,\ 2^{k+1}-1]\)，共有 \(2^k\) 个数，且每一项满足：

\[\frac{1}{\sqrt{i}} \le \frac{1}{\sqrt{2^k}} = 2^{-k/2} \]

所以该区间和 \(\le 2^k \cdot 2^{-k/2} = 2^{k/2}\)。

对所有 \(k\) 求和（从 \(0\) 到 \(\lfloor \log_2 m \rfloor\)）：

\[ \sum_{k=0}^{\lfloor \log_2 m \rfloor} 2^{k/2} = O\left(2^{(\log_2 m)/2}\right) = O(\sqrt{m}) \]

引理得证。 \(\square\)

二、情况一：不做任何预处理

杜教筛递归需要计算所有状态 \(\left\lfloor \frac{n}{i} \right\rfloor\)。以 \(\sqrt{n}\) 为分界线分成两类。

1. 小状态：\(x \le \sqrt{n}\)

共有 \(\sqrt{n}\) 个状态，单个状态 \(S(x)\) 的整除分块代价为 \(O(\sqrt{x})\)。

因为 \(x \le \sqrt{n}\)，所以 \(\sqrt{x} \le n^{1/4}\)。总代价为：

\[ \sum_{x=1}^{\sqrt{n}} O(\sqrt{x}) \le \sum_{x=1}^{\sqrt{n}} O(n^{1/4}) = O(\sqrt{n} \cdot n^{1/4}) = O(n^{3/4}) \]

2. 大状态：\(x > \sqrt{n}\)

此时 \(x = \left\lfloor \frac{n}{i} \right\rfloor\)，且 \(i < \sqrt{n}\)。总代价为：

\[ \sum_{i=1}^{\sqrt{n}} O\left(\sqrt{\frac{n}{i}}\right) = O\left(\sqrt{n} \sum_{i=1}^{\sqrt{n}} \frac{1}{\sqrt{i}}\right) \]

套用引理（令 \(m = \sqrt{n}\)）：

\[ = O\left(\sqrt{n} \cdot n^{1/4}\right) = O(n^{3/4}) \]

结论：两部分相加，无预处理时总复杂度为：

\[\boxed{O(n^{3/4})} \]

三、情况二：预处理前 \(K\) 项

线性预处理出 \(S(1)\) 到 \(S(K)\)，直接查表不递归，预处理代价为：

\[O(K) \]

递归部分只计算 \(x > K\) 的状态，即 \(i < \frac{n}{K}\)。递归代价为：

\[ \sum_{i=1}^{n/K} O\left(\sqrt{\frac{n}{i}}\right) = O\left(\sqrt{n} \sum_{i=1}^{n/K} \frac{1}{\sqrt{i}}\right) \]

再次套用引理（令 \(m = \frac{n}{K}\)）：

\[ = O\left(\sqrt{n} \cdot \sqrt{\frac{n}{K}}\right) = O\left(\frac{n}{\sqrt{K}}\right) \]

因此总代价函数为：

\[T(K) = O\left(K + \frac{n}{\sqrt{K}}\right) \]

四、证明 \(K = n^{2/3}\) 是最优阈值

1. 先证下界：任何 \(K\) 都有 \(T(K) \ge n^{2/3}\)

分两种情况讨论：

若 \(K \le n^{2/3}\)，则 \(\frac{n}{\sqrt{K}} \ge \frac{n}{\sqrt{n^{2/3}}} = n^{1 - 1/3} = n^{2/3}\)，故 \(T(K) \ge n^{2/3}\)。
若 \(K \ge n^{2/3}\)，则直接有 \(K \ge n^{2/3}\)，故 \(T(K) \ge n^{2/3}\)。

所以无论如何，都有：

\[T(K) \ge n^{2/3} \]

也就是说，复杂度不可能低于 \(n^{2/3}\)。