OI数学专题笔记 - 3
积性函数
-
如果函数 f 满足 gcd(a,b)=1 时有 f(ab)=f(a)f(b) ,则 f 叫做积性函数。
-
如果取消互质的条件则叫做完全积性函数。
例如:
莫比乌斯函数:
对于 μ(n) ,先对 n 分解质因数为 n=p1k1⋅p2k2⋯prkr
则
μ(n)=⎩⎨⎧1,n=1(−1)r,k1=k2=⋯=kr0,kt>1
莫比乌斯函数接下来会经常用到。
狄利克雷卷积
定义
定义:对于两个数论函数 f 和 g ,这两个函数的卷积 (f∗g)(n)=Σd∣nf(d)g(dn)
这个定义的含义为,对两个数论函数 f 和 g 在 n 上进行卷积,则枚举 n 的每一个因子进行计算求和。
性质
-
交换律: f∗g=g∗f
-
结合律: (f∗g)∗h=f∗(g∗h)
-
分配律: (f+g)∗h=f∗h+g∗h
恒等式
-
μ∗I=ϵ ( ϵ(n)=[n=1],I(n)=1 , 即当 n=1 成立时,ϵ(n)=1 ,否则等于 0 )
-
ϕ∗I=id ( id(n)=n )
-
μ∗id=ϕ
莫比乌斯反演
意思就是: 如果 g=f∗I ,则 f=μ∗g
BSGS算法
大小步算法,又称“北上广深算法”“阿姆斯特朗算法”“拔山盖世算法”。
数论问题:给定 a,b,p ,其中 p≤109 且为质数 ,求 ax≡b(modp) 的一组解。
对于 ax≡b(modp) ,一定有 x≤p−1 。当 x=p 时,根据费马小定理 ap−1≡1(modp) ,则 ap≡a1(modp) 。
按照解的范围每 p 分为一组,则第一组为 a1,a2,⋯,ap , 第二组为 ap+1,ap+2,⋯,a2p ,可以注意到第二组的每个数均等于上一个数的 ap 倍,则查看 b 在第 r,r>1 组是否出现过也就等价于查看 a(r−1)pb 使用逆元取模后,在第一组有没有出现过。