素数

1 单判

1.1 基础判断方法O( $\sqrt{n}$ )

从2到 $\sqrt{n}$ 搜一遍,如果能整除就不是质数。

1.2 Miller-Rabin

运用fermat小定理

$$\because IsPrime(n)$$

$$gcd(n,a)==1$$

$$\therefore a^{n-1}\equiv1\pmod{n}$$

2 线筛

2.1 埃氏筛法 $\Theta(n(ln)^2 n)$

2.2 欧拉筛 $\Theta(n)$

逆元/同余

1 定义

$a\equiv b\pmod{n}$ 表示在模n意义上a与b同余

$a\ast n\equiv 1\pmod{p}$ 表示a与n互为逆元

2 线性筛法

$A(i)=-(\frac{p}{i})\times A(P\space\bmod\space i)$

特殊数

1 斐波那契数列

$$f(0)=0$$

$$f(1)=1$$

$$f(n)=f(n-1)+f(n-2)(n>=2)$$

2 卡特兰数

$$h(0)=1$$

$$h(1)=1$$

$$h(n)=\sum_{i=0}^{n-1}h(i)h(n-1-i)$$

3 卡迈克尔数

这个数会卡Miller_Rabin算法

所以在判的时候需要二次判断

如果p是素数且0<x<p,则方程x^2%p=1的解为x=1或x=p-1.

$$\because IsPrime(p)$$

$$0<x<p$$

$$x^2\bmod p=1$$

$$\therefore x=1||p-1$$

积性函数

一个具有可乘性的函数称为积性函数

1 狄利克雷卷积

若 $f(x)g(x)$ 均为积性函数,则

定义 $h=f\ast g$

$$h(x)=\sum_{d\vert n}f(d)g(\frac{n}{d})$$

h也为积性函数

2 欧拉函数

$$\varphi(x)=\sum_{i=1}^{x-1}[gcd(x,i)==1]$$

$\sum_{d|n}\varphi(d)=n$

3 莫比乌斯函数

4 莫比乌斯反演

对于两个函数 $f(x)$ 与 $F(x)$ ,若 $F(n)=\sum_{d\vert n}f(d)$ ,则 $f(n)=\sum_{d\vert n}\mu(d)F(\frac{n}{d})$

$\sum_{d|n}\mu(d)=[n=1]$

5 杜教筛

如果f*h=g

若h好求,G好求,那F也好求

$h(1)F(n)=G(n)-\sum_{i=2}^{n}h(i)F(\frac{n}{i})$

$\Sigma(n)=\sum_{i=1}^{n}i\lfloor\frac{n}{i}\rfloor$

$\phi(n)=\frac{n(n+1)}{2}-\sum_{i=2}^{n}\phi(\lfloor\frac{n}{i}\rfloor)$

$M(n)=1-\sum_{i=2}^{n}M(\lfloor\frac{n}{i}\rfloor)$