数学相关的学习笔记
还没写完.....
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\)。
狄利克雷卷积
定义： $ (fg)(n)=_{d|n}f(d)g() $
由于\(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)={i=0}^ng(i)g(n)={i=0}n(-1){n-i}f(i) $
生成函数：$f=g e^x g=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_1a_n},(S)=_{TS}(T)(-1)^{|T|-1} $
证明：
甚至还有个更厉害的第\(k\)大反演 实际上这个可以：
\(\textrm{kth}(k,S)=\sum\limits_{T\subset S}\min(T)(-1)^{|T|-k}\binom{|T|-1}{k-1}\)