[省选]数学知识整理

### 素数 #### 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)$