数学相关的学习笔记

还没写完…..

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^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=[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}$

斯特林反演

# 数学

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×