寒假集训数学知识

寒假集训数学知识

一、素数

1.素数计数函数

素数计数函数记为\(\pi(x)\),表示小于等于\(x\)的素数的个数,即:

\[\pi(x)=\{n|n\leq x且n为素数\} \]

素数定理:当\(x\)很大时,\(\pi(x)\)近似等于\(\frac{x}{\ln x}\),即:

\[\lim_{x\to+\infty}\pi(x)=\frac{x}{\ln x} \]

2.唯一分解定理与标准分解式

唯一分解定理:对于自然数\(N>1\),如果\(N\)不为质数,那么\(N\)可以唯一分解成有限个质数的乘积,即:

\[N=\prod^k_{i=1}{a_i}^{p_i} \]

这样的分解称为标准分解式

3.Eratosthenes筛法

基本思想:任意整数\(x\)的倍数都不是质数

对于每个数\(x\),只需要从\(x^2\)开始标记

时间复杂度\(O(n\log \log n)\)

int primes[N],cnt;
bool st[N];
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]){
			primes[cnt++]=i;
			for(int j=i;j<=n/i;j++)
				st[j*i]=true;
		}
	}
}

4.线性筛法

基本思想:在每个数的最小质因子处标记

时间复杂度\(O(n)\)

int primes[N],cnt;
bool st[N];
void get_primes(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]) primes[cnt++]=i;
		for(int j=0;primes[j]<=n/i;j++){
			st[primes[j]*i]=true;
			if(i%primes[j]==0) break;
		}
	}
}

二、因数

1.因数的一些基本常识

寒假集训数学知识

  • 前\(16\)个质数乘积\(>10^{18}\)

2.分解质因数

枚举\(2\)~\(\sqrt n\),分解结果为\(\prod {p_i}^{k_i}\)

int primes[N],k[N];
void divide(int n){
	for(int i=2;i<=n/i;i++)
		if(n%i==0){
			int s=0;
			while(n%i==0){
				n/=i;
				s++;
			}
			primes[++cnt]=i;
			k[cnt]=s;
		}
	if(n>1){
		primes[++cnt]=n;
		k[cnt]=1;
	}
}

3.枚举所有因数

在分解质因数的基础上可以达到\(O(\)因数个数\()\)

int divisors[N],primes[N],k[N];
int cntprime,cntdiv;
void dfs(int p,int s){
	if(p>cntp){
		divisors[++cnt]=s;
		return;
	}
	for(int i=0;i<=k[p];i++){
		dfs(p+1,s);
		s*=primes[p];
	} 
}

三、剩余系运算

1.取模(mod)

概念:求两个数相除的余数

基本运算:

\((a+b)\%p=(a\%p+b\%p)\%p\)
\((a-b)\%p=(a\%p-b\%p)\%p\)
\((a\times b)\%p=(a\%p\times b\%p)\%p\)
\((a^b)\%p=((a\%p)^b)\%p\)

除法利用逆元计算

\(a\div b=a\times b^{-1}\space (mod\space p)\)

2.快速幂

求\(a^b\%p\)

运用二进制拆分思想\(O(\log b)\)

int qpow(int a,int b,int p){
	int res=1%p;//防止qpow(1,0,1)时出错
	while(b){
		if(b&1)	res=(ll)res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

3.欧几里得算法(GCD)

int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

4.最小公倍数

\[lcm(a,b)=\frac{ab}{gcd(a,b)} \]

可以用欧几里得算法求\(gcd(a,b)\)后求\(lcm(a,b)\)

5.扩展欧几里得算法(EXGCD)

常用于求\(ax+by=gcd(a,b)\)的一组可行解\((x,y)\)
证明:

根据裴蜀定理,可以找到\(x_1,y_1,x_2,y_2\)使得

\[\begin{cases} ax_1+by_1=gcd(a,b)\\ bx_2+(a-b\lfloor\frac{a}{b}\rfloor)y_2=gcd(b,a-b\lfloor\frac{a}{b}\rfloor)\\ \end{cases} \]

成立,根据欧几里得算法,这两个式子右侧是相等的,则有:

\[ax_1+by_1=bx_2+(a-b\lfloor\frac{a}{b}\rfloor)y_2 \]

整理得:

\[a(x_1-y_2)+b[y_1-(x_2-\lfloor\frac{a}{b}\rfloor y_2)]=0 \]

我们希望等式对于任意\(a,b\)都成立,则有:

\[x_1=y_2,y_1=(x_2-\lfloor\frac{a}{b}\rfloor y_2) \]

这样,求解\(x_1,y_1\),只需求解\(x_2,y_2\),所以可以进行递归,下面寻找边界条件。

不难发现当\(b=0\)时,一组解为\(x=1,y=0\).

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

6.Stein算法

用于处理高精度\(gcd\)

当两个数同为偶数时,cnt++,任意一个为偶数时,这个数除以\(2\),同为奇数时,采取更相减损术,最终结果为\(2^{cnt}\cdot a\)(\(a\)为剩下的数)

7.费马小定理

\(a^p=a\) \((mod\) \(p)\)

8.剩余系求逆元

对于某个\(a\),是否存在\(b\),使得\(ab=1\) \((mod\) \(p)\)

存在性:当且仅当\(gcd(a,p)=1\)时有逆元

证明:考虑\(ax+py=1\)的解

唯一性:逆元若存在,一定唯一

法一:费马小定理

要求\(p\)为质数

\(a\cdot a^{p-2}=1\) \((mod\) \(p)\)

逆元即为\(a^{p-2}\)

法二:EXGCD

考虑求\(ax+my=1\)的解

法三:线性求逆元1

求出\(1,2,\cdots,n\)中每个数关于\(p\)的逆元

首先:$$1^{-1}=1\space(mod\space p)$$

其次对于所求的\(i^{-1}\),我们设:

\[p=k\cdot i+r\space(1<r<i<p) \]

再把这个式子放到\(mod\space p\)意义下我们可以得到:

\[k\cdot i+r=0\space (mod\space p) \]

两边同时乘\(i^{-1}*r^{-1}\)可以得到:

\[k\cdot r^{-1}+i^{-1}=0\space(mod\space p) \]

化简得:

\[i^{-1}=-k\cdot r^{-1}=-\lfloor\frac{p}{i}\rfloor\cdot (p\space mod\space i)^{-1}\space(mod\space p) \]

求\(1\)~\(n\)在\(mod\space p\)意义下的逆元:

int inv[N];
void inverse(int n,int p){
	inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=(LL)(p-p/i)*inv[p%i]%p;
}

法四:线性求逆元2

上面的方法只能求出\(1,2,\cdots,n\)的逆元,而不能求给定任意\(n\)个数的逆元

求给定任意\(n\)个数\((1<a_i<p)\)的逆元方法如下:

  1. 计算\(n\)个数\(mod\space p\)意义下的前缀积,记为\(s_i\)
  2. 使用扩展欧几里得算法或者快速幂求出\(s_n\)的逆元,记作\(sv_n\)
  3. 由于\(sv_n\)是\(n\)个数前缀积的逆元,所以\(sv_n\)也是\(n\)个数逆元的前缀积,当我们把\(sv_n\)再乘上\(a_n\)时,就会与\(a_n\)的逆元抵消,变为前\(n-1\)个数逆元的前缀积,记为\(sv_{n-1}\)
  4. 同理进行如上\(n-1\)次迭代,就能得到每个数逆元的前缀积,记为\(sv_i\)
  5. 最后每个数的逆元就可以用\(s_{i-1}\cdot sv_i\space mod \space p\)求得

时间复杂度\(O(n+\log p)\)

int n,p;
int a[N],s[N],sv[N],inv[N];
void inverse(){
	s[0]=1;
	for(int i=1;i<=n;i++)
		s[i]=a[i]*s[i-1]%p;
	sv[n]=qpow(s[n],p-2,p);//快速幂
	for(int i=n-1;i>=1;i--)
		sv[i]=sv[i+1]*a[i+1]%p;
	for(int i=1;i<=n;i++)
		inv[i]=sv[i]*s[i-1]%p;
}

9.中国剩余定理(CRT)

对于以下线性同余方程组:

\[\begin{cases} x=b_1\space(mod\space a_1)\\ x=b_2\space(mod\space a_2)\\ \vdots\\ x=b_n\space(mod\space a_n)\\ \end{cases} \]

其中所有\(a_i\)互质,求\(x\)?

显然有无数解,且所有解都是由最小的正解\(a+k\cdot lcm(a_1,a_2,\cdots,a_n)\)得到

那么最小的正解\(a\)怎么求呢?

结论:在\(lcm(a_1,a_2,\cdots,a_n)\)的剩余系下,有唯一解:

\[\sum_{i=1}^nb_i\cdot M_i\cdot {M_i}^{-1} \]

其中,\(M_i=\prod_{j\neq i} a_j\),\({M_i}^{-1}\)为\(M_i\)在\(mod\space a_i\)意义下的逆元

证明(不如说是理解):以三个线性同余方程为例,根据上方结论可得以下结果:

\[x=b_1\cdot a_2a_3\cdot (a_2a_3)^{-1}+b_2\cdot a_1a_3\cdot (a_1a_3)^{-1}+b_3\cdot a_1a_2\cdot (a_1a_2)^{-1} \]

因为\(x\)的第\(2,3\)项含有因数\(a_1\),则有:

\[x=b_1\cdot a_2a_3\cdot (a_2a_3)^{-1}\space (mod\space a_1) \]

又因为\((a_2a_3)^{-1}\)恰好是在\(mod\space a_1\)意义下的逆元,则有:

\[a_2a_3\cdot(a_2a_3)^{-1}=1\space(mod\space a_1) \]

因此可得:

\[x=b_1\space(mod\space a_1) \]

同理易证得:

\[\begin{cases} x=b_2\space(mod\space a_2)\\ x=b_3\space(mod\space a_3)\\ \end{cases}\]

由上述方法可知,我们在\(lcm(a_1,a_2,\cdots,a_n)\)的剩余系内找到了唯一解\(x\)

10.扩展中国剩余定理(EXCRT)

对于以下线性同余方程组

\[\begin{cases} x=b_1\space(mod\space a_1)\\ x=b_2\space(mod\space a_2)\\ \vdots\\ x=b_n\space(mod\space a_n)\\ \end{cases} \]

其中\(a_i\)可能不互质,求\(x\)?

注意:当\(a_i\)不互质时,可能无解。

解决方法:将线性同余方程两两合并

考虑两个式子:

\[\begin{cases} x=b_1\space(mod\space a_1)\\ x=b_2\space(mod\space a_2)\\ \end{cases} \]

我们将其改写为:

\[\begin{cases} x=a_1k_1+b_1\\ x=a_2k_2+b_2\\ \end{cases} \]

则有:

\[a_1k_1+b_1=a_2k_2+b_2 \]

移项得:

\[a_1k_1+a_2k_2=b_2-b_1 \]

注意:我们这里将负号给了\(k_2\),中间用加号连接。

我们可以利用\(exgcd\)得到\(a_1k_1+a_2k_2=gcd(a_1,a_2)\)的一组解,此时若想让原方程有解,只需\(gcd(a_1,a_2)\mid(b_2-b_1)\),此时方程的一组解为\(exgcd\)的解分别乘\(\frac{b_2-b_1}{gcd(a_1,a_2)}\)

解出\(k_1,k_2\)后,再将其代回,得到\(x\),那么这两个同余方程就可以合并成一个同余方程:

\[x=x_0\space(mod\space lcm(a_1,a_2)) \]

注意:这里的\(x_0\)为上面的两个同余方程解出的最小的正解\(x\)

根据上述方法进行\(n-1\)次合并,若出现\(gcd(a_1,a_2)\nmid (b_2-b_1)\),则证明方程组无解,若没有出现以上情况,则原线性同余方程组的解为最终合并成一个同余方程后的\(x_0\)

四、欧拉函数相关

1.定义

表示小于等于\(n\)的与\(n\)互质的数的个数,记作\(\phi(n)\)

欧拉函数是积性函数

2.相关公式

(1) \(\phi(mn)=\phi(m)\phi(n)\space(gcd(m,n)=1)\)(此处为积型函数性质)

证明:

考虑构造两个集合使得两个集合的理论大小分别为\(\phi(mn)\)和\(\phi(m)\phi(n)\),构造如下:

\[A=\{x\mid gcd(x,mn)=1\}\\ B=\{(a,b)\mid gcd(a,m)=1,gcd(b,n)=1\}\\ \]

此时只需证明两个集合等势(大小相等)即可

证明等势分为两步:

  1. \(\forall a_1,a_2\in A,a_1\neq a_2,f(a_1)\neq f(a_2)\) 由此可推出\(size(A)\leq size(B)\)
  2. \(\forall b\in B,\exists a\in A,f(a)=b\) 由此可推出\(size(B)\leq size(A)\)

注意:这里\(f\)只是对应函数,无实际意义。

从而可以得到两个集合等势

证明\((1)\)如下:

利用反证法,若\((1)\)不成立,任取\(x_1,x_2\in A\)且满足\((1)\)条件,则\(x_1,x_2\)对应到集合\(B\)中的数对分别为:

\((x_1\space mod \space m,x_1\space mod \space n),(x_2\space mod \space m,x_2\space mod \space n)\)

令数对第一维为\(y_1\),第二维为\(y_2\),可以构造出如下同余方程组:

\[\begin{cases} x=y_1\space(mod\space m)\\ x=y_2\space(mod\space n)\\ \end{cases} \]

根据中国剩余定理可知,方程组有唯一确定的\(x\leq lcm(m,n)\),故假设不成立,\((1)\)成立

证明\((2)\)如下:

\(\forall (a,b)\in B\),对应到集合\(A\)的数应满足:

\[\begin{cases} x=a\space(mod\space m)\\ x=b\space(mod\space n)\\ \end{cases} \]

同理可得方程组有唯一确定的\(x\leq lcm(m,n)\),故\((2)\)成立

从而我们得到集合\(A\)与集合\(B\)等势,从而证明\(\phi(mn)=\phi(m)\phi(n)\space(gcd(m,n)=1)\)

(2) \(n=\sum_{d|n}\phi(d)\)

简单证明:

以\(n=8\)为例,作出如下数列:

\[\begin{matrix} \frac{1}{8}&\frac{2}{8}&\frac{3}{8}&\frac{4}{8}&\frac{5}{8}&\frac{6}{8}&\frac{7}{8}&\frac{8}{8}&\\ \end{matrix} \]

将分数化简,并按分母相同排在同一行,删去非最简分数后可得:

\[\begin{matrix} \frac{1}{8}&&\frac{3}{8}&&\frac{5}{8}&&\frac{7}{8}&&\\ &\frac{1}{4}&&&&\frac{3}{4}&&&\\ &&&\frac{1}{2}&&&&&\\ &&&&&&&\frac{1}{1}&\\ \end{matrix} \]

我们发现,各行的分母为整数\(n\)互不相同的因数\(d_i\),且分母为\(d_i\)的一行的所有分子\(a_i\)恰好满足\(gcd(a_i,d_i)=1\),所以分母为\(d_i\)的一行恰好包含\(\phi(d_i)\)个最简分数,又因为在一开始的数列中,未化简的分数有\(n\)个,从而可以推出:\(n=\sum_{d|n}\phi(d)\)

(3) \(a^{\phi(n)}=1\space(mod\space n)\space(gcd(a,n)=1)\)

注:本条为欧拉定理

(4) \(\phi(p^k)=p^k-p^{k-1}\space(p\)为质数\()\)

3.求欧拉函数的值

\[\phi(n)=n\prod^{s}_{i=1}({1-\frac{1}{p_i}}) \]

推导方法:利用容斥原理

int phi(int n){
	int ans=n;
	for(int i=2;i<=n/i;i++)
		if(n%i==0){
			ans=ans/i*(i-1);
			while(n%i==0) n/=i;
		}
	if(n>1) ans=ans/n*(n-1);
	return ans;
} 

4.扩展欧拉定理

\[a^b\space mod\space p= \begin{cases} a^{b\space mod \space\phi(p)},&gcd(a,p)=1\\ a^b,&gcd(a,p)\neq1,b\leq \phi(p)\\ a^{(b\space mod\space\phi(p))+\phi(p)},&gcd(a,p)\neq1,b\geq \phi(p)\\ \end{cases} \]

五、组合数学

1.排列数

从\(n\)个不同元素中,任取\(m\)个元素的所有排列的个数,用符号\(A_n^m\)表示

\[A_n^m=\frac{n!}{(n-m)!} \]

2.组合数

从\(n\)个不同元素中,任取\(m\)个元素的所有组合的个数,用符号\(C_n^m\)或\(\begin{pmatrix}n\\m\end{pmatrix}\)表示

\[\begin{pmatrix}n\\m\end{pmatrix}=C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!} \]

在所有排列中,每个组合都有\(m!\)个

3.二项式定理

\[(a+b)^n=\sum_{i=0}^n\begin{pmatrix}n\\i\end{pmatrix}a^{n-i}b^i \]

4.多重全排列问题

引入:从\(n\)个物品(其中含\(a_i\)个物品\(i\))中选择\(m\)个物品,有多少种方案?

思路:把\(n\)个物品当作互不相同,排列方式有\(n!\)种,又因为每个物品出现\(a_i!\)次重复,结果即为:

\[\frac{n!}{\prod a_i!} \]

5.整数划分问题

引入:有\(n\)个球,把它们放在\(m\)个盒子中,使得每个盒子都不空,有多少种分法?

思路:将\(m-1\)个板放在\(n-1\)个空隙中,结果为\(\begin{pmatrix}n-1\\m-1\end{pmatrix}\)

拓展:如果可以有空盒子呢?

思路\(1\):可以将两个板放在同一个空隙中

思路\(2\):将问题转化为\(n+m\)个球放在\(m\)个盒子中,每个盒子都不空,结果为\(\begin{pmatrix}n+m-1\\m-1\end{pmatrix}\)

例题:\(x_1+x_2+\cdots+x_k=r\)的非负整数解的数目:

\[\begin{pmatrix}r+k-1\\k-1\end{pmatrix} \]

6.第二类斯特林数

将\(n\)个物品划分成\(k\)个非空的没有区别的集合的方案数。

递推公式为:

\[S2(i,j)=S2(i-1,j)\cdot j+S2(i-1,j-1) \]

通项公式:

\[S2(n,m)=\frac{1}{m!}\cdot \sum_{k=0}^m(-1)^k\begin{pmatrix}m\\k\end{pmatrix}(m-k)^n \]

7.贝尔数

第二类斯特林数第二维前缀和,即:

\[B_n=\sum_{k=1}^nS2(n,k) \]

递推公式:

\[B_{n+1}=\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}B_k \]

即枚举包含最后一个元素的集合大小

8.Lucas定理

求组合数(模较小质数)

公式:

\[\begin{pmatrix}n\\m\end{pmatrix}mod\space p=\begin{pmatrix}\lfloor\frac{n}{p}\rfloor\\\lfloor\frac{m}{p}\rfloor\end{pmatrix}\begin{pmatrix}n\space mod \space p\\m\space mod \space p\end{pmatrix}mod\space p \]

前者进行递归,后者可以预处理出阶乘

9.扩展Lucas定理

当\(p\)不为质数时,往往使用中国剩余定理将问题转化为模质数次幂,最后合并

\[lucas(n,p^k)=lucas(\lfloor\frac{n}{p}\rfloor,p^k)B^{\lfloor\frac{n}{p^k}\rfloor}_{p^k-1}B_{n\space mod \space p^k} \]

六、莫比乌斯反演

(以下为 1.30 数学知识 补充笔记)

1.前置知识

(1)一些引理

引理1:

\(\lfloor\frac{a}{bc}\rfloor=\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor\)

引理2:

对于任意\(n,d\in \Z\),\(\lfloor\frac{n}{d}\rfloor\)的取值最多有\(2\sqrt{n}\)个

(2)数论分块

(3)积性函数

定义:若函数\(f(x)\)满足当\(gcd(x,y)=1\)时,\(f(xy)=f(x)f(y)\),则称\(f(x)\)为积性函数

特别地,当函数\(f(x)\)满足\(\forall x,y\in\Z\),\(f(xy)=f(x)f(y)\),则称\(f(x)\)为完全积性函数

(4)狄利克雷卷积

上一篇:复旦大学2018--2019学年第二学期(18级)高等代数II期末考试第六大题解答


下一篇:条件期望习题