【专题总结】数学（未完）

前言

老年人的一些整理。。（复习用）

完全剩余系

1.从模 (n) 的每个剩余类中各取一个数，得到一个由 (n) 个数组成的集合，叫做模 (n) 的一个完全剩余系。完全剩余系常用于数论中存在性证明。
2.对于 (n) 个整数，其构成模n的完系等价于其关于模 (n) 两两不同余
3.若 (a_i(1leq ileq n)) 构成模 (n) 的完系，(k,min Z) , ((n,m)=1) ,则 (k+mcdot a_i) 也构成完系。【NOIP2017】小凯的疑惑
4.若 (a_i(1leq ileq n)) 构成模 (n) 的完系，则 (sum_{i=1}^{n}a_i) 。

快速幂

code

LL qpow(LL x,LL y,LL P){
	LL re=1;
	while(y){
		if(y&1) re=re*x%P;
		x=x*x%P;y>>=1;
	}
	return re%P;
}

素数定理

1.设 (x>0) ，以 (pi(x)) 表示不超过 (x) 的素数个数，当 (x ightarrow +infty) 时，(pi(x) ightarrow Li(x)) 或 (pi(x) ightarrow frac{x}{ln(x)})
2.各范围素数数量

威尔逊定理

((p-1)!) (equiv) (p-1) ((mod) (p)) ( (p) 是质数)

线性筛

1.效率是 (O(n)) 的，并且每个合数只会被其最小的质因数筛到。

code

bool is_pri[N+10];
int pri[N],cntp=0;
void init_pri(){
	for(int i=2;i<=N;++i){
		if(!is_pri[i]) {
			pri[++cntp]=i;
		}
		for(int j=1;j<=cntp&&pri[j]*i<=N;++j){
			is_pri[pri[j]*i]=1;
			if(i%pri[j]==0) {
				break;
			}
		}
	}
}

乘法逆元

1.线性求逆元：令 (p=k*i+r) ((p是质数,k=lfloor frac{p}{i} floor)) ，显然 (k*i+requiv0(mod) (p)) , 移项得 (i^{-1}equiv(-k)cdot r^{-1}(mod) (p))

code

LL inv[N+10];
void init_inv(){
	inv[0]=inv[1]=1;
	for(LL i=2;i<=N;++i) inv[i]=(P-P/i)*inv[P%i]%P;
}

2.快速幂求逆元：由费马小定理 (a^{p-1}equiv1(mod) (p)) ，得 (a^{p-2}equiv a^{-1}(mod) (p))
3.扩展欧几里得求逆元。（感觉没什么用啊。。）

排列组合（部分公式）

1.({n choose m}) (=) (frac {n!}{m!(n-m)!})

2.({n choose m}) (=) ({n-1 choose m-1}) + ({n-1 choose m})

3.(sum_{i=0}^{n}{n choose i}) (=) (2^{n})

4.(sum_{i}{n choose i}{m choose k-i}) (=) ({n+m choose k}) 在 (n) 个中选 (i) 个，再在另外 (m) 个中选剩余 (k-i) 个，每种 (i) 的情况加起来，相当于是在 (n+m) 中选 (k) 个。

5.(sum_{i}{i choose k}{n-i choose m-k}) (=) ({n+1 choose m+1}) 相当于在 (n+1) 个中取 (m+1) 个，然后对于每个 (i) 就对应着将选出的第 (k+1) 个点当做分割点后得到的方案。

6.(sum_{i=0}^{x-1}{k+i choose i}) (=) ({k+x choose k+1}) 国庆校考的时候用到的式子，当时是oeis出来的，不会证明，但还是记一下吧。

7.李善兰恒等式（感觉没什么用。。）

一些比赛遇到的奇怪式子

1.(y^{d(y)}) (=) (prod_{t|y} y) (=) (prod_{t|y} t cdot frac{y}{t}) (=) (prod_{t|y} t^{2})