数学相关的学习笔记
还没写完.....
gcd
$\gcd(a,b,c)=\gcd(\gcd(a,b),c)$
显然。
$\gcd(a,b)=\gcd(a,b\pm a)$。
因为任何$a,b$的公因数都是$a\pm b$的因数。
$\gcd(n,m)|\gcd(n,mk)$。
事实上 $\gcd(n,mk)=\gcd(n,m)\gcd(\frac{n}{\gcd(n,m)},k)$。
若$\gcd(n,k)=1$，$\gcd(n,mk)=\gcd(n,m)$。
这是上面的特殊情况。显然$n$和$mk$的公因数是$m$的因数，因为不可能是$k$的因数。
若$x>1$，则$\gcd(x^a-1,x^b)=1$
若$a\ge b$，则$\gcd(x^a-1,x^b)|\gcd(x^a-1,x^bx^{a-b})=\gcd(x^a-1,x^a)=\gcd(x^a-1,1)=1$。
否则$\gcd(x^a-1,x^b)=\gcd(x^a-1,x^ax^{b-a})=\gcd(x^a-1,x^{b-a})$。
$\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1$
$$ x^b-1=(x^a-1)x^{b-a}+x^{b-a}-1\\ \gcd(x^a-1,x^b-1)=\gcd(x^a-1,(x^a-1)x^{b-a}+x^{b-a}-1)=\gcd(x^a-1,x^{b-a}-1) $$
exgcd
求$ax+by=d$的一组解，其中$d=\gcd(a,b)$。
假设已经得到了$(a\bmod b)x_1+by_1=d$，则$(a-\lfloor\frac{a}{b}\rfloor b)x_1+by_1=d$
合并$b$得到$x_1a+(y_1-\lfloor\frac{a}{b}\rfloor x_1)b=d$。
lcm
$\textrm{lcm}(a,b,c)=\textrm{lcm}(\textrm{lcm}(a,b),c)$。
显然。
$\textrm{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$
显然。
当然这就不能求$\textrm{lcm}(a,b,\dots)\bmod p$了。因为$\gcd(a,b)\not=\gcd(a\bmod p,b\bmod p)$。
但我们还有可以取膜的方法：
$\textrm{lcm}(S)=\prod\limits _{T \subset S}\gcd(T)^{(-1)^{|T|+1}}$
考虑lcm的本质：
$\textrm{lcm}(\prod p_i^{a_i},\prod p_i^{b_i})=\prod p_i^{\max(a_i,b_i)}=\prod \textrm{lcm}(p_i^{a_i},p_i^{b_i})$。
所以说可以对每一个$p_i$拆开算，然后最后$p_i$的系数就是每一项$p_i$系数取$\max$，这东西本质就是个$\min-\max$容斥。
斐波那契数列
定义
$$ f_n=\begin{cases}0 & n=0\\1 & n=1\\f_{n-1}+f_{n-2} & n>1\end{cases} $$
性质
$\gcd(f_a,f_{a+1})=1$。
首先$a=0$时成立。
假设$a=k-1$时成立，则$\gcd(f_k,f_{k+1})=\gcd(f_{k},f_{k-1}+f_k)=\gcd(f_k,f_{k-1})=1$得到$a=k$也成立。
$f_{n+m}=f_{n+1}f_m+f_nf_{m-1}$。
考虑转移矩阵。
$$ \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix} \begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix}= \begin{bmatrix}f_{n}\\f_{n-1}\end{bmatrix}\\ \begin{bmatrix}1 & 1\\1& 0\end{bmatrix}= \begin{bmatrix}f_2 & f_1\\f_1& f_0\end{bmatrix}\\ \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^n= \begin{bmatrix}f_{n+1} & f_n\\f_n & f_{n-1}\end{bmatrix}\\ \begin{bmatrix}f_{n+1} & f_n\\f_n & f_{n-1}\end{bmatrix} \begin{bmatrix}f_{m+1} & f_m\\f_m & f_{m-1}\end{bmatrix}= \begin{bmatrix}f_{n+m+1} & f_{n+m}\\f_{n+m} & f_{n+m-1}\end{bmatrix}= \begin{bmatrix}f_{n+1}f_{m+1}+f_nf_m & f_{n+1}f_m+f_nf_{m-1}\\f_nf_{m+1}+f_{n-1}f_m & f_nf_m+f_{n-1}f_{m-1}\end{bmatrix} $$
则得证。
对于任意$a,b$，$\gcd(f_a,f_b)=f_{\gcd(a,b)}$。
$$ \begin{align} \gcd(f_a,f_b) &=\gcd(f_a,f_{b-a+1}f_a+f_{b-a}f_{a-1})\\ &=\gcd(f_a,f_{b-a}f_{a-1})\\ &=\gcd(f_a,f_{b-a}) \end{align} $$
故得证。
类似物
考虑类似于斐波那契数列的东西：
$$ f_n=\begin{cases}0 & n=0\\1 & n=1\\af_{n-1}+bf_{n-2} & n>1\end{cases} $$
其中$\gcd(a,b)=1$。
性质$1$显然一样。
考虑性质$2$：
$$ \begin{bmatrix}a & b\\1 & 0\end{bmatrix} \begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix}= \begin{bmatrix}f_{n}\\f_{n-1}\end{bmatrix}\\ \begin{bmatrix}a & b \\ 1 & 0\end{bmatrix}= \begin{bmatrix}f_2 & bf_1\\f_1& bf_{0}\end{bmatrix}\\ \begin{bmatrix}a & b \\ 1 & 0\end{bmatrix}^n= \begin{bmatrix}f_{n+1} & bf_n\\f_n& bf_{n-1}\end{bmatrix}\\ \begin{bmatrix}f_{n+1} & bf_n\\f_n & bf_{n-1}\end{bmatrix} \begin{bmatrix}f_{m+1} & bf_m\\f_m & bf_{m-1}\end{bmatrix}= \begin{bmatrix}f_{n+m+1} & bf_{n+m}\\f_{n+m} & bf_{n+m-1}\end{bmatrix}= \begin{bmatrix}f_{n+1}f_{m+1}+bf_nf_m & bf_{n+1}f_m+b^2f_nf_{m-1}\\f_nf_{m+1}+bf_{n-1}f_m & bf_nf_m+b^2f_{n-1}f_{m-1}\end{bmatrix} $$
所以$f_{n+m}=f_{n+1}f_m+bf_nf_{m-1}$。
考虑性质3：
$$ \begin{align} \gcd(f_a,f_b) &=\gcd(f_a,f_{a+1}f_{b-a}+bf_af_{b-a-1})\\ &=\gcd(f_a,f_{b-a}f_{a+1})\\ &=\gcd(f_a,f_{b-a}) \end{align} $$
发现一样。
中国剩余定理（CRT）
普通版
求$x$使
$$ \begin{cases} x\equiv a_1 \pmod {p_1}\\ x\equiv a_2 \pmod {p_2}\\ \vdots\\ x\equiv a_n \pmod {p_n}\\ \end{cases} $$
其中对于任意$i\not=j,\gcd(p_i,p_j)=1$。
显然$x$在$\bmod \prod p_i$意义下有唯一解。
令$P=\prod p_i$。
求$b_i$使得$b_i \frac{P}{p_i}\equiv 1 \pmod{p_i}$，
那么答案就为$\sum a_ib_i\frac{P}{p_i}$。
扩展
若$p_i$可能不互质，怎么办？
方法1：直接拆。
把每个数分解质因数拆成$x\equiv a_i\pmod {p_i^{k_i}}$。
如果出现$p_i$相同，合并并判断是否合法。
当然直接分解不可能的，这辈子不可能的。
由于$\textrm{lcm}(p_1\dots p_n)$不会很大，所以可以先把$\textrm{lcm}(p_1\dots p_n)$分解质因数，得到的不同质因子不会很多，分解$p_i$的时候就可以直接用这些质因数试除了。
方法2：用exgcd合并。
已知$\begin{cases}x\equiv a_1\pmod{p_1}\\x\equiv a_2\pmod{p_2}\end{cases}$
则$x=a_1+b_1p_1=a_2+b_2p_2$，
则$b_1p_1+b_2p_2=a_1-a_2$。
然后可以用exgcd解出$b_1,b_2$。比上面那两个不知道高到哪里去了。
费马-欧拉定理
原定理
若$a,n$互质，则$a^{\varphi(n)}\equiv 1\pmod n$，其中$\varphi(n)$表示小于$n$与$n$互质的数。
证明：设$R=\{x_1\dots x_{\varphi(n)}\}$为小于$n$与$n$互质数的集合。
则$aR=\{ax_1\dots ax_{\varphi(n)}\}$。
事实上$aR$在$\bmod n$意义下和R是同一个集合。
显然$aR$中的数全部和$n$互质（根据$\gcd$的性质）。
并且不存在$x_i\not=x_j$使得$ax_i\equiv ax_j\pmod n$。
否则显然$a(x_i-x_j)\equiv 0\pmod n$。
由于$a,n$互质，则$(x_i-x_j)\equiv 0\pmod n$，则$x_i=x_j$与条件不符。
显然两个集合是相同的，它们的元素乘积也是相同的。
$\prod\limits _{i=1}^{\varphi(n)} x_i\equiv \prod\limits _{i=1}^{\varphi(n)} ax_i \pmod n$，则$a^{\varphi(n)}\equiv 1 \pmod n$。
得证。
特殊的，若$n$为质数，则$a^{n-1}\equiv 1\pmod n$。
扩展
一般的，若$b\ge \varphi(n)$，则$a^b\equiv a^{\varphi(n)+b\bmod \varphi(n)}\pmod n$
引理1：
$\begin{cases}x\equiv a\pmod {P_1}\\x\equiv a\pmod {P_2}\end{cases}$则$x\equiv a\pmod {\textrm{lcm}(P_1,P_2)}$。
首先$P_1=\prod p_i^{b_i},P_2=\prod p_i^{c_i}$
则$x\equiv a\pmod {p_i^{b_i}},x\equiv a\pmod {p_i^{c_i}},x\equiv a\pmod {p_i^{\max(b_i,c_i)}}$。
所以$x\equiv a\pmod {\prod p_i^{\max(b_i,c_i)}}$，显然$\prod p_i^{\max(b_i,c_i)}=\textrm{lcm}(P_1,P_2)$。
引理2：
若p为质数，$k\ge 1$则$\varphi(p^k)\ge k$。
$\varphi(p^k)=p^{k-1}(p-1)$，当$p\ge 2$时，显然$p^{k-1}\ge k$。其中当$p=2,k=2$或$k-1$时取到。
引理3：
若$\gcd(a,b)=1$，$\varphi(a)\varphi(b)=\varphi(ab)$。
由$\varphi$的定义可证。
当$n=p^k$时（$p$是质数）
若$a,p$互质，则$a^b\equiv a^{b\bmod \varphi(p^k)}\equiv a^{b\bmod \varphi(p^k)+\varphi(p^k)}$。
否则，设$a=xp$，则$a^b= x^bp^b$,由于$b\ge \varphi(p^k)\ge k$，显然两边都$=0$，得证。
对于一般的$n$，把它分解质因数成$\prod p_i^{k_i}$，显然$a^b\equiv a^{b\bmod \varphi(p_i^{k_i})+\varphi(p_i^{k_i})}\equiv a^{b\bmod \varphi(n)+\varphi(n)}\pmod {p_i^{k_i}}$，由引理1得证。
积性函数
定义
若一个数论函数$f(x)$满足若$(a,b)=1$则$f(ab)=f(a)f(b)$则f被称为积性函数。
若一个数论函数$f(x)$满足$f(ab)=f(a)f(b)$则f被称为积性函数。
常见积性函数（令$n=p_1^{e_1}p_2^{e_2}p_3^{e_3}\dots p_k^{e_k}$）：
- 单位元 $\epsilon(n) = [n = 1]$
- 1函数$1(n)=1$
- Id函数$Id(n)=n$
- 莫比乌斯函数$\mu(n)=[\max(e_1,e_2\dots e_k)\le 1](-1)^k$。
- 欧拉函数$\varphi(n)=n\prod(1-\frac{1}{p_i})$。
- 约数个数函数$d(n)=\sum\limits_{d|n}1$。
- 约数和函数$\sigma(n)=\sum\limits_{d|n}d$。
- 刘维尔函数$\lambda(n)=(-1)^k$。
狄利克雷卷积
定义： $ (f\ast g)(n)=\sum_{d|n}f(d)g(\frac{n}{d}) $
由于$f,g$都是积性函数，所以显然$f\ast g$也是。
性质：
$f\ast \epsilon=f$
显然吧
$\mu\ast1=\epsilon$
考虑$n=p^k$。
则$\sum_{i=0}^k\mu(p^i)=\mu(1)+[k>0]\mu(p)=1+[k>0](-1)=[k=0]=\epsilon(p^k)$。
根据积性显然成立。
$\varphi\ast1=Id$
考虑$n=p^k$。
则$\sum_{i=0}^k\varphi(p^i)=1+\sum_{i=1}^k(p-1)p^{i-1}=p^k=Id(p^k)$。
根据积性显然成立。
$1\ast1=d$
根据定义。
$d(xy)=\sum_{i|x}\sum_{j|y}[(i,j)=1]$
考虑$x=p^a,y=p^b$，显然$xy$的因数包括了$1,p^1,\dots p^a,p^{a+1}\dots a^{a+b}$。
每个$[(i,j)=1]$的$i,j$显然都可以表示$\frac{iy}{j}$这样一个因数。
根据积性显然成立。
$\sigma(xy)=\sum_{i|x}\sum_{j|y}[(i,j)=1]\frac{iy}{j}$
同上改成了求和。
莫比乌斯反演
若$f\ast 1=g$则$f=g\ast \mu$。
原理：$f\ast 1 \ast \mu =f\ast \epsilon=f=g\ast \mu$。
组合数
$\binom{n}{m}=\frac{n!}{m!(n-m)!}$。
Lucas定理
问题：求$\binom{n}{m}\bmod p$，其中$n,m\le 10^{18},p\le 10^6$且$p$为质数。
若$n=a_0+a_1p+a_2p^2+a_3p^3+\dots$,$m=b_0+b_1p+b_2p^2+b_3p^3+\dots$，其中$a_0,a_1\dots,b_0,b_1\dots <p$，则$\binom{n}{m}=\prod \binom{a_i}{b_i}$。
证明：
定义两个多项式模p同余当且仅当每项系数模p同余。
对于$1\le x\lt p$，$\binom{p}{x}=\frac{p}{x}\binom{p-1}{x-1}$显然模p为0.
显然$(1+x)^p=\sum\limits_{i=0}^p\binom{p}{i}x^i=1+x^p$。
那么
$$ \begin{align} (1+x)^n&=(1+x)^{a_0}(1+x)^{pa_1}(1+x)^{p^2a_2}\dots\\ &\equiv (1+x)^{a_0}(1+x^p)^{a_1}(1+x^{p^2})^{a_2}\dots \pmod p \end{align}\\ $$
$$ \begin{align} \binom{n}{m}x^m&=\binom{n}{m}x^{b_0}\cdot x^{pb_1}\cdot x^{p^2b_2}\dots\\ &\equiv \binom{a_0}{b_0}x^{b_0}\binom{a_1}{b_1}x^{pb_1}\binom{a_2}{b_2}x^{p^2b_2} \pmod {p} \end{align} $$
证毕。
ExLucas定理
与前者唯一关系在于都是求组合数$\bmod p$，其它没了。
若$p$不为质数，则Lucas定理就没用了。
ExLucas是这样的：
首先将$p$分解质因数，最后CRT合并回来。
然后问题在于求$\binom{n}{m}\bmod p^k$其中$p$是质数。
然后我们需要求$n!$分解质因数后$p$的个数以及去掉$p$后的值$f(n)\bmod p^k$。
$p$个数很好做，但是问题在于去掉$p$后的值。
由于$p^k$不大，我们可以先预处理$a_i=1$到$i$中不是$p$倍数数的积$\bmod p^k$。($i\le p^k$)
$$ f(n)=f(\lfloor \frac{n}{p}\rfloor)a_{p^k}^{\lfloor \frac{n}{p^k}\rfloor}a_{n\bmod p^k} $$
基本组合恒等式
主要是组合意义感性理解？
$\sum_{i=0}^n \binom{n}{i}=2^n$
n个物品任意选出一些有$2^n$种方案，其中可以选$0\dots n$个物品。
$\sum_{i=0}^n\binom{i}{x}=\binom{n+1}{x+1}$
有$n+1$个物品，选$x+1$个。
枚举选择的编号最大的物品是哪个。
$\sum_{i=0}^n\binom{k+i}{i}=\binom{k+n+1}{n}$
考虑杨辉三角。
$\binom{n}{m}=\sum_{i=0}^m\binom{m}{i}\binom{n-m}{m-i}$
有$n$个物品选$m$个，枚举前$m$个物品中有几个被选取。
※斯特林数
第一类斯特林数
定义：${n\brack m}$表示将$n$个物品分成$m$个无序非空环的方案数。
${n\brack m}={n-1\brack m-1}+(n-1){n-1\brack m}$
就是说，考虑第$n$个物品可以单独放进一个环，或者放在另外任意一个物品后面。
生成函数相关：
$$ x^{\overline{n}}=\sum_{i=0}^n{n\brack i}x^i\\ x^{\underline{n}}=\sum_{i=0}^n(-1)^{n-i}{n\brack i}x^i\\ $$
考虑DP求$x^{\overline{n}},x^{\underline{n}}$两个多项式的每项系数的过程。
第二类斯特林数
定义：$n\brace m$表示将$n$个物品分成$m$个无序非空集合的方案数。
${n \brace m} = {n-1 \brace m-1} + m{n-1 \brace m}$
就是说，考虑第$n$个物品，可以是唯一一个元素一组，也可以放进这$m$组中的任意一组、
生成函数相关：
$x^n=\sum\limits_{i=0}^n{n\brace i}x^{\underline{i}}$
把$n$个物品分进$x$个有序可空集合的方案数。
枚举有几个集合非空。
$m!{n\brace m}=\sum\limits _{i=0}^m(-1)^{m-i}{m\choose i}i^n$
把$n$个物品分成$m$个无序非空集合，容斥枚举有几个集合一定是空的。选出这些集合以后其它集合随便放。
于是这就是有序非空集合的方案数了。然后再除$m!$。
(FFT警告)
常见反演
莫比乌斯反演
$f\ast 1=g \Rightarrow g\ast \mu = f$
刚说过了。
二项式反演
$f(n)=\sum\limits_{i=0}^n\binom{n}{i}g(i)\Rightarrow g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i) $
生成函数：$\hat f=\hat g e^x \Rightarrow \hat g=\hat f e^{-x} $
正常证明：
$$ \begin{aligned} g(n)&=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}\sum_{j=0}^i\binom{i}{j}g(j)\\ &=\sum_{i=0}^n(-1)^{n-i}\sum_{j=0}^i\binom{n}{i}\binom{i}{j}g(j)\\ &=\sum_{i=0}^n(-1)^{n-i}\sum_{j=0}^i\binom{n}{n-j}\binom{n-j}{n-i}g(j)\\ &=\sum_{j=0}^ng(j)\binom{n}{n-j}\sum_{i=j}^n(-1)^{n-i}\binom{n-j}{n-i}\\ &=\sum_{j=0}^ng(n-j)\binom{n}{j}\sum_{i=0}^j(-1)^i\binom{j}{i}\\ &=\sum_{j=0}^ng(n-j)\binom{n}{j}[j=0]\\ &=g(n) \end{aligned} $$
QAQ
Min-Max反演
$S=\{a_1\dots a_n\},\max(S)=\sum\limits_{T\subset S}\min(T)(-1)^{|T|-1} $
证明：
甚至还有个更厉害的第$k$大反演 实际上这个可以：
$\textrm{kth}(k,S)=\sum\limits_{T\subset S}\min(T)(-1)^{|T|-k}\binom{|T|-1}{k-1}$