寒假集训数学知识
一、素数
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)\)的逆元方法如下：
- 计算\(n\)个数\(mod\space p\)意义下的前缀积，记为\(s_i\)
- 使用扩展欧几里得算法或者快速幂求出\(s_n\)的逆元，记作\(sv_n\)
- 由于\(sv_n\)是\(n\)个数前缀积的逆元，所以\(sv_n\)也是\(n\)个数逆元的前缀积，当我们把\(sv_n\)再乘上\(a_n\)时，就会与\(a_n\)的逆元抵消，变为前\(n-1\)个数逆元的前缀积，记为\(sv_{n-1}\)
- 同理进行如上\(n-1\)次迭代，就能得到每个数逆元的前缀积，记为\(sv_i\)
- 最后每个数的逆元就可以用\(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\}\\ \]此时只需证明两个集合等势(大小相等)即可
证明等势分为两步：
- \(\forall a_1,a_2\in A,a_1\neq a_2,f(a_1)\neq f(a_2)\) 由此可推出\(size(A)\leq size(B)\)
- \(\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)\)为完全积性函数