数论随记

· · 个人记录

模块一 基础数论

素数

素数，指的是除 1 和它本身之外没有其他约数的数。

求素数

求不超过 n 的所有素数可以用 O(n) 的 \rm{Euler} 筛法。

其思想是枚举每个数的最小素因子。

（代码见数论函数模块 \rm{Euler} 函数部分的 \rm{Euler} 筛法）

素数计数函数

令素数计数函数 \pi(n) 表示不超过 n 的素数个数。我们有如下的 素数定理：

\pi(n)\approx \frac{n}{\ln n}

推论：

素数计数

利用 \rm{Euler} 筛法筛出 n 以内的所有素数可在 O(n) 内求出 \pi(n)。

用一种类似积性函数求和的筛法可以达到 O(\frac{n^{3/4}}{\log n}) 的时间复杂度，先进的做法可以达到 O(\frac{n^{2/3}}{\log n})。

算数基本定理

又称唯一分解定理。

该定理指出：任意一个正整数 n 都可以表示成素数的乘积的形式：

n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}

式中 p_1,...,p_s 是不同素数。且不计次序的情况下，这一表达是唯一的。

取整函数

对于实数 x，记 \left\lfloor x\right\rfloor 为不超过 x 的最大整数。

$$\left\lfloor x\right\rfloor\leq x < \left\lfloor x\right\rfloor+1$$ 对于正整数 $n$，$1$ 到 $n$ 中 $d$ 的倍数有 $\left\lfloor \frac{n}{d}\right\rfloor$ 个。 ### 取值个数 对于正整数 $n$，考虑当 $1 \leq d \leq n$ 时，$\left\lfloor \frac{n}{d}\right\rfloor$ 的不同的取值个数。 若 $d \leq \sqrt n$，则能得到的 $\left\lfloor \frac{n}{d}\right\rfloor$ 只有不超过 $\sqrt n$ 种。 若 $d > \sqrt n$，则 $\left\lfloor \frac{n}{d}\right\rfloor \leq \frac{n}{d} < \sqrt n$，又因为 $\left\lfloor \frac{n}{d}\right\rfloor$ 是正整数，故此时可能的取值也不超过 $\sqrt n$ 种。 综上，$\left\lfloor \frac{n}{d}\right\rfloor$ 可能的取值不超过 $2 \sqrt n$ 种。 ------------ ## 数论分块 数论分块可以快速计算一些含有除法向下取整的和式（即形如 $\sum_{i=1}^nf(i)\left\lfloor \dfrac{n}{i}\right\rfloor$ 的和式）。当可以在 $O(1)$ 内计算 $f(r)-f(l)$ 时，数论分块就可以在 $O(\sqrt n)$ 的时间内计算上述和式的值。 **结论**： 对于常数 $n$，使得式子 $$\left\lfloor \dfrac{n}{i}\right\rfloor=\left\lfloor \dfrac{n}{j}\right\rfloor$$ 成立的最大的满足 $i \leq j \leq n$ 的 $j$ 的值为 $\left\lfloor \dfrac n{\left\lfloor \frac ni\right\rfloor}\right\rfloor$。即值 $\left\lfloor \dfrac{n}{i}\right\rfloor$ 所在的块的右端点为 $\left\lfloor \dfrac n{\left\lfloor \frac ni\right\rfloor}\right\rfloor$。 **证明** 令 $k=\left\lfloor \dfrac{n}{i}\right\rfloor$，可以知道 $k \leq \dfrac ni \begin{aligned} &\therefore \left\lfloor \dfrac nk\right\rfloor \geq \left\lfloor \dfrac n{\left\lfloor \frac ni\right\rfloor}\right\rfloor=\left\lfloor i\right\rfloor=i\\ &\therefore j=i_{\max}=\left\lfloor \dfrac nk\right\rfloor=\left\lfloor \dfrac n{\left\lfloor \frac ni\right\rfloor}\right\rfloor\\ &&\square \end{aligned}

数论分块的过程大致如下：考虑和式

\sum_{i=1}^nf(i)\left\lfloor \dfrac{n}{i}\right\rfloor

我们知道 \left\lfloor \dfrac{n}{i}\right\rfloor 的值成一个块状分布（就是同样的值都聚集在连续的块中），那么就可以用数论分块加速计算，降低时间复杂度。

利用上述结论，我们先求出 f(i) 的前缀和（记作 s(i)=\sum_{j=1}^if(j)），然后每次以 [l,r]=[l,\left\lfloor \dfrac n{\left\lfloor \frac nl\right\rfloor}\right\rfloor] 为一块，分块求出贡献累加到结果中即可。

例题

UVA11526 H(n)

题意：

T$ 组数据，每组一个整数 $n$。对于每组数据，求出 $\sum_{i=1}^n\left\lfloor \dfrac{n}{i}\right\rfloor

思路：

运用数论分块，将每一块相同的 \left\lfloor \dfrac{n}{i}\right\rfloor 一起计算，时间复杂度 O(T\sqrt n)。

P2261 [CQOI2007]余数求和

题意：

给定 n 与 k，求 \sum_{i=1}^nk \bmod i

思路：

推柿子：

\begin{aligned} \sum_{i=1}^nk \bmod i & = \sum_{i=1}^n(k-i\times \left\lfloor \dfrac{k}{i}\right\rfloor)\\ & = \sum_{i=1}^nk- \sum_{i=1}^n(i\times \left\lfloor \dfrac{k}{i}\right\rfloor)\\ &=n\times k - \sum_{i=1}^n(i\times\left\lfloor \dfrac{k}{i}\right\rfloor) \end{aligned}

然后数论分块直接做就行了，时间复杂度 O(\sqrt {\min (n,k)})。

模块二 数论函数

定义域为正整数、值域是复数的子集的函数称为数论函数。

OI 中研究的数论函数的值一般也是整数。

积性函数

设 f 是数论函数，若对任意互素的正整数 a,b 都有 f(ab)=f(a)f(b)，则称 f 是积性函数。

若对任意的正整数 a,b 都有 f(ab)=f(a)f(b)，则称 f 是完全积性函数。

若 f 是积性函数，且 n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s} 是 n 的标准分解，则有

f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})\cdots f(p_s^{\alpha_s})

因此研究积性函数 f 可转化为研究 f(p^{\alpha})，即 f 在素数和素数的幂上的取值。

积性函数求值

设 f 是积性函数，为求 f(n)，可以对 n 分解素因子，然后计算所有的 f(p^{\alpha}) 并乘起来。

如果要对 1 到 n 之间的所有数求出 f，注意到 \rm{Euler} 筛法的过程中可以求出每个数的最小素因子和最小素因子的幂次，利用此就能在线性时间内计算出所需的 f 的值。

单位函数

单位函数 \epsilon(n) 定义为：

\epsilon(n)=[n=1]= \begin{cases} 1, & n = 1; \\ 0, & n \neq 1. \end{cases}

单位函数是完全积性函数。

除数函数

除数函数 \sigma_k(n) 用来表示 n 的因子的 k 次方之和：

\sigma_k(n)=\sum_{d\mid n}{d^k}

约数个数 \sigma_0(n) 常记为 d(n)，约数和 \sigma_1(n) 常记为 \sigma(n)。

除数函数都是积性函数。

筛法求约数个数

借助算数基本定理的推论，有

d(n)=\prod_{i=1}^s{d(p_i^{\alpha_i})}=\prod_{i=1}^s(\alpha_i+1)

然后我们就能实现一个能在 O(n) 内求出 1 到 n 内所有数的约数个数的筛法（其中 num_i 表示 i 的最小素因子幂次）：

int cnt;
int d[N], pri[N], num[N];
bool vis[N];

inline void Sieve (int n)
{
    d[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (! vis[i])  d[i] = 2, num[i] = 1, pri[++cnt] = i;
        for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
        {
            vis[i * pri[j]] = true;
            if (i % pri[j] == 0)
            {
                num[i * pri[j]] = num[i] + 1;
                d[i * pri[j]] = d[i] / num[i * pri[j]] * (num[i * pri[j]] + 1);
                break;
            }
            num[i * pri[j]] = 1;
            d[i * pri[j]] = d[i] * 2;
        }
    }
}

\rm{Euler} 函数

由 $n$ 的标准分解并结合容斥原理，我们可以得到 $\rm{Euler}$ 函数的显示表达式： $$\varphi(n)=n\cdot\prod_{i=1}^s{\Big(1-\frac{1}{p_i}\Big)}$$ 其中 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}$ 是 $n$ 的标准分解。 由此易见 $\rm{Euler}$ 函数是积性函数。 ### $\rm{Euler}$ 函数性质 - 对于所有素数 $p$，有 $\varphi(p)=p-1

证明

显然。

\rm{Euler} 反演

利用 \rm{Euler} 函数的一条性质：n=\displaystyle\sum_{d\mid n}\varphi(d)

将式中的 n 换为其它东西，有时可以加速求解。

例题：

P2303 [SDOI2012] Longge 的问题

P3166 [CQOI2014]数三角形

\rm{Euler} 定理

若 \gcd(a,m)=1，则 a^{\varphi(m)}\equiv 1 \pmod m

当 m 为素数时，\varphi(m)=m-1，所以有 a^{m-1}\equiv 1 \pmod m，此时的 \rm{Euler} 定理即为费马小定理。

证明详见 OI Wiki。

扩展 \rm{Euler} 定理

a^b \equiv \begin{cases} a^{b \bmod \varphi(m)},&\gcd(a,m)=1,\\ a^b,&\gcd(a,m) \ne 1,b < \varphi(m),\\ a^{(b\bmod \varphi(m))+\varphi(m)},&\gcd(a,m) \ne 1,b \geq \varphi(m). \end{cases} \pmod m

模板：P5091 【模板】扩展欧拉定理

\rm{Euler} 筛法

利用 \rm{Euler} 筛法可用 O(n) 的时间复杂度求出 1 到 n 内的所有素数及所有数的 \rm{Euler} 函数。

模板：SP4141 ETF - Euler Totient Function

int cnt;
int pri[N], phi[N];
bool vis[N];

inline void Euler_Sieve (int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (! vis[i])  pri[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
        {
            vis[i * pri[j]] = true;
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            phi[i * pri[j]] = phi[i] * phi[pri[j]];
        }
    }
}

当然通过 \rm{Euler} 函数的显示表达式，也可以实现一个 O(\sqrt n) 的求单点 \rm{Euler} 函数的算法。

模板：UVA10299 Relatives（本题在 n=1 时需输出 0）

inline int phi (int n)
{
    int ans = n;
    for (int i = 2; i <= sqrt (n); i++)
    {
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)  n /= i;
        }
    }
    return n > 1 ? ans / n * (n - 1) : ans;
}

\rm{Dirichlet} 卷积

设 f,g 是数论函数，考虑数论函数 h 满足

h(n)=\sum_{d\mid n}f(d)g(\frac nd)

则称 h 为 f 和 g 的 \rm{Dirichlet} 卷积，记作 h = f \ast g。

注意 h(n)=\displaystyle\sum_{d\mid n}f(d)g(\frac nd) 等价于 h(n)=\displaystyle\sum_{i\times j=n}f(i)g(j)，而后一种形式具有一个很漂亮的对称的性质，利用此可以证明 \rm{Dirichlet} 卷积满足交换律与结合律。

\rm{Dirichlet} 卷积性质

单位函数 \epsilon 是 \rm{Dirichlet} 卷积的单位元，即对于任意函数 f，有 \epsilon \ast f=f \ast \epsilon = f。

如果 f,g 都是积性函数，那么 f \ast g 也是积性函数。

许多关系都可以使用 \rm{Dirichlet} 卷积来表示。

下面用 1 来表示取值恒为 1 的常函数，定义幂函数 {\rm Id}_k(n)=n^k，{\rm Id=Id}_1。

除数函数的定义可以写为：

\sigma_k=1 \ast {\rm Id}_k $${\rm Id}=\varphi \ast 1$$ ## $\rm{Mobius}$ 函数 $\rm{Mobius}$ 函数 $\mu(n)$ 定义为： $$ \mu(n)= \begin{cases} 1, & n = 1; \\ (-1)^s, & n = p_1p_2\cdots \ p_s; \\ 0, & \rm{otherwise}. \end{cases} $$ 其中 $p_i$ 为不同素数。 可以看出，$\mu(n)$ 恰在 $n$ 无平方因子时非零。 易见 $\mu$ 为积性函数。 ### $\rm{Mobius}$ 函数性质 $\rm{Mobius}$ 函数具有如下最重要的性质： $$\sum_{d\mid n}\mu(d)=\epsilon(n)$$ 使用 $\rm{Dirichlet}$ 卷积来表示，即 $$\mu \ast 1=\epsilon$$ **证明** $n=1$ 时显然成立。 若 $n>1$，设 $n$ 有 $s$ 个不同的素因子，由于 $\mu(d) \neq 0$ 当且仅当 $d$ 无平方因子，故 $d$ 中每个素因子的幂次只能为 $0$ 或 $1$。故有 $$\sum_{d\mid n}\mu (d)=\sum_{k=0}^s(-1)^k\binom{s}{k}=(1-1)^s=0$$ ### 筛法求 $\rm{Mobius}$ 函数 使用线性筛可在 $O(n)$ 内求出 $1$ 到 $n$ 中所有数的 $\rm{Mobius}$ 函数。 ```cpp int cnt; int mu[N], pri[N]; bool vis[N]; inline void Sieve (int n) { mu[1] = 1; for (int i = 2; i <= n; i++) { if (! vis[i]) pri[++cnt] = i, mu[i] = -1; for (int j = 1; j <= cnt && i * pri[j] <= n; j++) { vis[i * pri[j]] = true; if (i % pri[j] == 0) break; mu[i * pri[j]] = -mu[i]; } } } ``` ### $\rm{Mobius}$ 变换 设 $f$ 为数论函数，定义函数 $g$ 满足 $$g(n)=\sum_{d\mid n}f(d)$$ 则称 $g$ 是 $f$ 的 $\rm{Mobius}$ 变换，$f$ 是 $g$ 的 $\rm{Mobius}$ 逆变换。 用 $\rm{Dirichlet}$ 卷积表示即为 $g=f\ast 1$。 ### $\rm{Mobius}$ 反演 $\rm{Mobius}$ 反演定理指出，上式成立的充要条件为： $$f(n)=\sum_{d\mid n}\mu(\frac nd)g(d)$$ 即 $f=g\ast \mu$。 利用其可以解决一系列求和问题，常见的做法是使用一个 $\rm{Dirichlet}$ 卷积替换求和式中的一部分，然后调换求和顺序，最终降低时间复杂度。 经常利用的卷积有 $\mu \ast 1=\epsilon$ 与 ${\rm{Id}}=\varphi \ast 1$（后者即为 $\rm{Euler}$ 反演）。