数论虽然在 NOIP 中不作深入的要求,但是在这之上的比赛就经常会有涉及到这类知识的算法题目。

本文来总结整理一下一些初等的数论知识。

{% blockquote 卡尔·弗里德里希·高斯 %} Mathematics is the queen of the sciences—and number theory is the queen of mathematics. 数学是科学的皇后,数论是数学的皇后。 {% endblockquote %}

基本定理和性质

本文所使用的符号均参照数学选修4-6

质数与合数

在大于 \(1\) 的自然数中,除了 \(1\) 和该数自身外,无法被其他自然数整除的数称为质数(aka. 素数)。 大于 \(1\) 的自然数若不是素数,则称之为合数(aka. 合成数)。 \(1\) 既不是质数,也不是合数。

最大公约数和最小公倍数

最大公约数(abbr. gcd, greatest common divisor)指能够整除多个整数的最大正整数。 如果 \(c\) 是 \(a\) 和 \(b\) 的最大公约数,我们记为 \((a, b) = c\)。 如果 \((a,b)=1\),那么我们称 \(a\) 与 \(b\) 互质,可以记为 \(a \bot b\)。

最小公倍数(abbr. lcm, least common multiple)指能够被多个整数整除的最小正整数。 如果 \(c\) 是 \(a\) 和 \(b\) 的最大公约数,我们记为 \([a, b] = c\)。

一个大家都知道的结论:\((a, b) \times [a, b] = ab\)

整除

如果 \(a\) 能够整除 \(b\),我们称 \(a\) 是 \(b\) 的约数因子,记为 \(a \mid b\)。 相反,如果 \(a\) 不能够整除 \(b\),我们记为 \(a \nmid b\)。

整除有一些优秀的性质:

  • \(a \mid b, b \mid c, a \bot b \Rightarrow ab \mid c\)
  • \(a \mid bc, a \bot b \Rightarrow a \mid c\)
  • \(a \mid bc \Rightarrow a \mid b\) 或 \(a \mid c\)

正确性显然。

Sum 和 Product

\[\sum_{i=1}^{n}a_i = a_1 + a_2 + ... + a_n\] \[\prod_{i=1}^{n}a_i = a_1 a_2 ... a_n\]

算数基本定理

设 \(n>1\),则 \(n\) 可以分解成素数的乘积 \[ n = p_1p_2...p_k, \] 如果不计这些素数的次序,则分解式是唯一的。

设 \(n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\) 是 \(n\) 的标准分解式,若用 \(d(n)\) 表示 \(n\) 的所有正约数的个数,那么 \[d(n) = \prod_{i=1}^{k}(a_i+1)\]

组合数与阶乘

组合数(aka. 二项式系数) \(\binom{n}{m}\) 表示从 \(n\) 个本质不同的物品中选出 \(m\) 个物品的方案数(不计选择的顺序)。

\[\binom{n}{m} = \frac{n!}{(n-m)!m!}\] 其中 \[n!=\begin{cases}1,&n=0\\\\\prod_{i=1}^{n}i,&n>0\end{cases}\]

于是我们有递推式: \[\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}\]

二项式定理: \[(x+y)^n = \sum_{i=0}^{n}\binom{n}{i}x^{n-i}y^i\]

同余

如果 \(a\) 和 \(b\) 对 \(p\) 的余数相等,那么我们记为 \(a \equiv b \pmod p\)

数论函数

积性函数

如果 \(f(x)\) 是积性函数,那么对于 \(\forall a, b \in N, a \bot b\),满足 \(f(ab) = f(a)f(b)\)。

下面是一些常见的积性函数:

  • \(\sigma_k(n) = \sum_{d|n}d^k\)
  • \(d(n)=\sigma_0(n)\) 表示 \(n\) 的正因子个数
  • \(\sigma(n)=\sigma_1(n)\) 表示 \(n\) 的所有正因子的和
  • \(id_k(n)=n^k\)
  • \(l(n)=id_0(n)=1\)
  • \(id(n)=id_1(n)=n\)
  • \(\varepsilon(n)=\begin{cases}1,&n=1\\\\0,&n>1\end{cases}\)

欧拉函数

莱昂哈德·欧拉(1707-1783)

欧拉函数 \(\varphi(n)\) 表示小于 \(n\) 的与 \(n\) 互质的正整数的个数。

设 \(n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\),则有 \[\varphi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\]

\(\varphi(n)\) 是积性函数

欧拉定理:设 \(m>1\),\((a,m)=1\),则 \[a^{\varphi(m)} \equiv 1 \pmod m\]

如果 \(m\) 是质数,那么 \(\varphi(m)=m-1\),这其实就是费马小定理了。

皮埃尔·德·费马(1601-1665)

费马小定理:设 \(p\) 是质数,\((a,p)=1\),则 \[a^{p-1} \equiv 1 \pmod p\]

扩展欧拉定理: \[a^b \equiv \begin{cases} a^{b \mod \varphi(p)}, &a \bot p \\\\ a^{b} , &b < \varphi(p) \\\\ a^{b \mod \varphi(p) + \varphi(p)}, &b \geq \varphi(p) \end{cases} \pmod p\]

例题: 求 \[2^{2^{2^{...}}} \mod p\]

**解:**令 \[S = 2^{2^{2^{...}}}\] 则 \[S \equiv 2^{S \mod \varphi(p) + \varphi(p)} \pmod p\] 于是问题可以转化为求 \(S\) 对 \(\varphi(p)\) 取模的子问题。 以此类推,当模数为 \(1\) 时,答案显然为 \(0\)。 然后递归回去计算即可。

莫比乌斯函数

莫比乌斯函数 \(\mu(n)\) 的定义:

设 \(n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\),

\[ \mu(n) = \begin{cases} 1, & n = 1 \\\\ (-1) ^ k, & \forall a_i=1 \\\\ 0, & \exists a_i \gt 1 \end{cases} \]

\(\mu(n)\) 也是积性函数。

\[\sum_{d \mid n}\mu(d) = \varepsilon(n)\]

算法

狄利克雷卷积

约翰·彼得·古斯塔夫·勒
热纳·狄利克雷
(1805-1859)

如果 \(f(n),g(n)\) 是数论函数,令 \(h = f \times g\),则 \[h(n)=\sum_{d|n}f(d)g(\frac{n}{d})\]

狄利克雷卷积有一些优秀的性质:

  • 交换律 \(f\times g=g\times f\)
  • 结合律 \((f\times g)\times h=f\times (g\times h)\)
  • 分配律 \(f\times (g+h)=f\times g+f\times h\)
  • 单位元 \(\varepsilon\times f=f\)

一些公式:

  • \(d(n)=\sum_{d|n}l(d) \Leftrightarrow d = l \times l\)
  • \(\sigma(n)=\sum_{d|n}id(d) \Leftrightarrow \sigma = l \times id\)
  • \(\varepsilon(n)=\sum_{d|n}\mu(d) \Leftrightarrow \varepsilon = l \times \mu\)
  • \(\varphi(n)=\sum_{d|n}\mu(d)\frac nd \Leftrightarrow \varphi = \mu \times id\)
  • \(n=\sum_{d|n}\varphi(d) \Leftrightarrow id = l \times \varphi\)

莫比乌斯反演

如果 \(f(n),g(n)\) 是数论函数,则有

\[f(n)=\sum_{d \mid n}g(d) \Leftrightarrow g(n) = \sum_{d \mid n}\mu(d)f(\frac{n}{d})\]

证明:

\[\begin{aligned} f &= g \times l \\\\ f \times \mu &= g \times l \times \mu \\\\ f \times \mu &= g \times \varepsilon \\\\ f \times \mu &= g \end{aligned}\]

变形:

\[f(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} g(dk) \Rightarrow g(k) = \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)f(dk)\]

这怎么证啊。。。

**例题:**求 \((n \leq m)\) \[\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=k]\]

解: 设 \[f(k)=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=k]\\\\g(k)=\sum_{i=1}^{n}\sum_{j=1}^{m}[k \mid (i,j)]\] 则有 \[g(k)=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}f(dk)\] 根据莫比乌斯反演得 \[f(k) = \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)g(dk)\] 考虑如何计算 \(g(k)\),我们马上就能发现 \[g(k) = \left\lfloor \frac{n}{k} \right\rfloor\left\lfloor \frac{m}{k} \right\rfloor\] 所以 \[f(k) = \sum_{d=1}^{\lfloor\frac{n}{k}\rfloor} \mu(d)\left\lfloor \frac{n}{dk} \right\rfloor\left\lfloor \frac{m}{dk} \right\rfloor\] 直接计算是 \(O(n)\) 的,可以利用前缀和和分块的技巧优化到单次询问 \(O(\sqrt{n}+\sqrt{m})\)。

总结

如果你不知道一个公式怎么证明,那就打表 打表找规律大法好

文章写太长不好,剩下来的以后讲。 下次应该会多写几道例题。

别问我为什么退役了才写这个