数学(粗糙的笔记)

数论(整数和他们的函数)、组合计数、线性代数、群论

gcd lcm 倍数 同余

bsgs:给定质数p,给定a和b,有(a,p)=1。求最小非负整数x,使得\(a^x\equiv b \pmod p\)

首先有欧拉定理,\(a^{\phi(p)}\equiv 1 \pmod p\),当……p必须是质数,不是要用exbsgs

miller-rabin:快速判断一个数是否是素数

进行测试前只考虑奇数情况,有一个费马小定理的逆定理,对于任意素数p,\(\forall x\in [1,p-1]\),都有\(x^p\equiv x\pmod p\),而对于合数,这个等式不一定成立。有Camerial数如561也成立,但是是合数。

考虑\(x^2\equiv 1\pmod n\)的根,等价于\((x-1)(x+1)\equiv 0\pmod n\),若n为奇素数则\((x-1)\)和\((x+1)\)中必定有一个为0,二次方程则最多有两个根,即为\(1\)和\(-1\),若为奇合数则讨论变得复杂

二次探查……对于int32之内的数,a选取2,7,61即可;对于int64之内的数,选取前10个素数即可

pollard-rho:给定合数n,要对n质因数分解

随机基底a和c,生成序列\(x_0=a,x_i=x_{i-1}^2\)……生日悖论

线性筛

中国剩余定理:\[x\bmod p_1=x_1\\x\bmod p_1=x_1\\ \vdots\\ x\bmod p_n=x_n\],求……

二次剩余:给定y和奇质数p,求x,使得\(x^2\equiv y\pmod p\)……

积性函数

数论函数:定义域在正整数上,值域一般在整数上的函数

狄利克雷卷积:\((fg)(n)=\sum_{d|n}f(d)g(\frac{n}{d})\),枚举n的所有因子,两函数分别取值。如:\(fg[6]=f[1]\cdot g[6]+f[2]\cdot g[3]+f[3]\cdot g[2]+f[6]\cdot g[1]\),暴力计算复杂度\(O(n\ln n)\)

积性函数:\(\forall(a,b)=1,f(ab)=f(a)\cdot f(b)\),常见积性函数:
普通函数\[1(n)=1,id(n)=n,e(n)=[n=1]\] 除数函数\[\sigma_k(n)=\sum_{d|n}d^k\] 欧拉函数(1到n-1中和n互质数的个数)\[\phi(n)\] 莫比乌斯函数(如果n有质因子指数\(k_i\)大于2则为0,质因子个数\(m\)为奇数则为-1,偶数则为1)\[\mu(n)=[k_1\leq1][k_2\leq1]\cdots[k_m\leq1](-1)^m\]

积性函数的第一项一定为1,除了全是0的积性函数第一项可能是0

如果\(f,g\)是两个积性函数,那么他们的狄利克雷卷积\(h=fg\)也是积性函数:为了方便,n只有两个质因子,\(n=p_1^{k_1}p_2^{k_2}\),交换求和号合并:

\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d})\\=\sum_{i_1=0}^{k_1}\sum_{i_2=0}^{k_2}f(p_1^{i_1}p_2^{i_2})g(p_1^{k_1-i_1}p_2^{k_2-i_2})\\=\sum_{i_1=0}^{k_1}\sum_{i_2=0}^{k_2}f(p_1^{i_1})f(p_2^{i_2})g(p_1^{k_1-i_1})g(p_2^{k_2-i_2})\\=\sum_{i_1=0}^{k_1}f(p_1^{i_1})f(p_2^{i_2})+\sum_{i_2=0}^{k_2}g(p_1^{k_1-i_1})g(p_2^{k_2-i_2})\\=h(p_1^{k_1})h(p_2^{k_2})\]

考虑把\(\mu\)和1卷起来来证:\[\sum_{d|n}\mu{d}=[n=1]\Rightarrow\mu*1=e\]

用欧拉函数的性质直接证:\[\sum_{d|n}\phi(d)=n\Rightarrow\phi*1=id\]

怎么求\(\phi,\mu\)的前n项?线性筛的同时将一个质数计算它筛到的数的函数值即可
怎么求\(\phi,\mu\)的前n项和?杜教筛之类的\(O(n^{\frac{2}{3}})\)

原根

给定n,若a满足$(a,n)=1$并且$1,a,a^2,\cdots,a^{\Phi(n)-1}$在$\bmod n$下都互不相同,则称a是n的一个原根。

$2,4,p^n,2p^n$有原根,其中$p$是奇素数;若$n$有原根,则原根的数量为$\phi(\phi(n))$个

组合数学

组合数:\(C^m_n=\frac{n!}{m!(n-m)!}\),使用杨辉三角计算,也可以使用预处理阶乘和他的逆元

分块优化矩阵乘法递推

容斥原理

\(F(A\cup B\cup C)=F(A)+F(B)+F(C)-F(A\cap B)-F(A\cap C)-F(B\cap C)+F(A\cap B\cap C)\)

二项式反演

概率论

期望的线性性:求随机排列中逆序对的期望个数

\(E(x)=0\times P(x=0)+1\times P(x=1)+\cdots+n\times P(x=n)\),并不好算,

期望独立的事件可以分开考虑,

发表评论

电子邮件地址不会被公开。 必填项已用*标注