OI数学专题笔记 - 3

积性函数

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

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

例如:

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

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

莫比乌斯函数:
对于 μ(n)\mu(n) ,先对 nn 分解质因数为 n=p1k1p2k2prkrn = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}

μ(n)={1,n=1(1)r,k1=k2==kr0,kt>1\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.

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

狄利克雷卷积

定义

定义:对于两个数论函数 ffgg ,这两个函数的卷积 (fg)(n)=Σdnf(d)g(nd)(f * g)(n) = \Sigma_{d | n}{f(d)g(\frac{n}{d})}

这个定义的含义为,对两个数论函数 ffggnn 上进行卷积,则枚举 nn 的每一个因子进行计算求和。

性质

  • 交换律: fg=gff * g = g * f

  • 结合律: (fg)h=f(gh)(f * g) * h = f * (g * h)

  • 分配律: (f+g)h=fh+gh(f + g) * h = f * h + g * h

恒等式

  • μI=ϵ\mu * I = \epsilon ( ϵ(n)=[n=1],I(n)=1\epsilon(n) = [n = 1], I(n) = 1 , 即当 n=1n = 1 成立时,ϵ(n)=1\epsilon(n) = 1 ,否则等于 00 )

  • ϕI=id\phi * I = id ( id(n)=nid(n) = n )

  • μid=ϕ\mu * id = \phi

莫比乌斯反演

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

  • f(n)=Σdnμ(d)g(nd)f(n) = \Sigma_{d | n}\mu(d)g(\frac{n}{d})

意思就是: 如果 g=fIg = f * I ,则 f=μgf = \mu * g

BSGS算法

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

数论问题:给定 a,b,pa, b, p ,其中 p109p \leq 10^9 且为质数 ,求 axb(modp)a^x \equiv b \pmod p 的一组解。

对于 axb(modp)a^x \equiv b \pmod p ,一定有 xp1x \leq p - 1 。当 x=px = p 时,根据费马小定理 ap11(modp)a^{p - 1} \equiv 1 \pmod p ,则 apa1(modp)a^p \equiv a^1 \pmod p

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