OI数学专题笔记 - 3

积性函数

• 如果函数 $f$ 满足 $gcd(a, b) = 1$ 时有 $f(ab) = f(a)f(b)$ ，则 $f$ 叫做积性函数。

• 如果取消互质的条件则叫做完全积性函数。

例如：

• I(n) = 1, id(n) = n 这两个就是完全积性函数

• 欧拉函数 $\phi(n)$ ，莫比乌斯函数 $\mu$ 就是积性函数。

莫比乌斯函数：
对于 $\mu(n)$ ，先对 $n$ 分解质因数为 $n = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}$
则

$\mu(n) = \left \{ \begin{array}{l} 1, n = 1 \\ (-1)^r, k_1 = k_2 = \cdots = k_r \\ 0, k_t > 1 \end{array} \right.$

莫比乌斯函数接下来会经常用到。

狄利克雷卷积

定义

定义：对于两个数论函数 $f$ 和 $g$ ，这两个函数的卷积 $(f * g)(n) = \Sigma_{d | n}{f(d)g(\frac{n}{d})}$

这个定义的含义为，对两个数论函数 $f$ 和 $g$ 在 $n$ 上进行卷积，则枚举 $n$ 的每一个因子进行计算求和。

性质

• 交换律： $f * g = g * f$

• 结合律： $(f * g) * h = f * (g * h)$

• 分配律： $(f + g) * h = f * h + g * h$

恒等式

• $\mu * I = \epsilon$ ( $\epsilon(n) = [n = 1], I(n) = 1$ ， 即当 $n = 1$ 成立时，$\epsilon(n) = 1$ ，否则等于 $0$ )

• $\phi * I = id$ ( $id(n) = n$ )

• $\mu * id = \phi$

莫比乌斯反演

• 如果 $g(n) = \Sigma_{d | n}f(d)$

• 则 $f(n) = \Sigma_{d | n}\mu(d)g(\frac{n}{d})$

意思就是： 如果 $g = f * I$ ，则 $f = \mu * g$

BSGS算法

大小步算法，又称“北上广深算法”“阿姆斯特朗算法”“拔山盖世算法”。

数论问题：给定 $a, b, p$ ，其中 $p \leq 10^9$ 且为质数 ，求 $a^x \equiv b \pmod p$ 的一组解。

对于 $a^x \equiv b \pmod p$ ，一定有 $x \leq p - 1$ 。当 $x = p$ 时，根据费马小定理 $a^{p - 1} \equiv 1 \pmod p$ ，则 $a^p \equiv a^1 \pmod p$ 。

按照解的范围每 $\sqrt{p}$ 分为一组，则第一组为 $a^1, a^2, \cdots , a^{\sqrt{p}}$ ， 第二组为 $a^{\sqrt{p} + 1}, a^{\sqrt{p} + 2} , \cdots , a^{2\sqrt{p}}$ ，可以注意到第二组的每个数均等于上一个数的 $a^{\sqrt{p}}$ 倍，则查看 $b$ 在第 $r, r > 1$ 组是否出现过也就等价于查看 $\frac{b}{a^{(r - 1)\sqrt{p}}}$ 使用逆元取模后，在第一组有没有出现过。