OIer的数学基础（持续更新中）

2023-12-25 13:14:16

0. 前言
求导
约数和定理
Lucas组合数定理

0. 前言

build at 20210730

篇幅有限，加减乘除什么的自行度娘就好了。
~~本文针对初中OIer~~

设$P=\{x|x\mbox{是质数}\}$

求导

update 20210730

一个平面中，两点确定一条直线
一条直线有斜率
斜率有一个快捷的计算公式
根据点斜式

\[y_1 - y_2 = k(x_1 - x_2) \]

可得

\[k = \frac{d y}{d x} \]

这里$d$表示$\Delta$，也就是变化的意思，不是变量（想当年这个把我坑了好久）
变化量，不是大的减小的，也不是小的减大的，而是前的减后的
（自己画个图算算就知道了）
然后，对于函数$f(x)$
他的导数用$f‘(x)$表示
现在我问你

若$f(x) = x$, $k$为多少？
就是1，这个很好算
若$f(x) = x^2$, $k$为多少？
很明显，不知道吧，没有一个固定的值
如果我们规定点$(x_0, y_0), (x_0 + dx, y_0 + dy)$都在这条函数上
求这两个点连线的斜率
很好算了吧
那么如果$dx$在慢慢缩小……
直到$dx$无限趋近于0
当然不是等于0，要不然斜率算不出来
那么我们就得到了导数的定义
当自变量的增量趋于零时，因变量的增量与自变量的增量之商的极限。

所以，可导的函数一定连续。不连续的函数一定不可导。
所以，

\[f‘(x) = \lim_{dx \rightarrow 0} \frac{dy}{dx} \]

更形象一点，函数$f$在$x$的导数等于这个点切线的斜率,也可以表示函数在这个点的变化情况。函数在这个点的导数越大，表示这个函数在这个点越陡（上升快）

函数$f(x) = x^2$在$A$点的导数就是上面经过$A$点直线的斜率，这个斜率为$2 \times x_A$
所以$f‘(1) = 2$, $f‘(2) = 4$$\dots$
然后你可能就会问，我怎么推导数？
不急不急，让我们先来看看，设$x_0, x = x_0 + \lim_{\Delta x \rightarrow 0} \Delta x, y_0 = f(x_0), y = f(x)$
那么就易得$f‘(x_0) = \frac{y - y_0}{x - x_0} = \frac{f(x) - f(x_0)}{x - x_0}$

零次函数
就是$y = C$, 这个时候$f(x_0) = f(x) = C, f‘(x_0) = 0$，也就是$y$随着$x$的变化为$0$
一次函数
$y = ax + b$, $f(x_0) = ax_0 + b, f(x) = ax + b, f(x) - f(x_0) = ax + b - ax_0 - b = a(x - x_0)$
$f‘(x_0) = \frac{a(x - x_0)}{x - x_0} = a$
好多次函数
设$f(x) = x^n$,

\[(x_0^n)‘ = \frac{x ^ n - x_0^n}{x - x_0}\= \frac{(x_0 + dx)^n - x_0^n}{dx} = \frac{k_1x_0^n + k_2x_0^{n-1}dx + k_3x_0^{n - 2}dx^2 + \dots + dx^n - k^nx_0^n}{dx}\= \frac{k_2x_0^{n - 1}dx + k_3x_0^{n-2}dx^2 + \dots + dx^n}{dx}\= {k_2x_0^{n-1} + k_3x_0^{n-2}dx + \dots \ dx^n} \tag(1) \]

这里根据的是杨辉三角拆出来的，$k_i$就表示杨辉三角第$n + 1$行第$i$个。推导过程如下：

根据二次项定理

其中每个为一个称作二项式系数的特定正整数，其等于。这个公式也称二项式公式或二项恒等式。
然后观察
= $C_{n}^{k}$
再根据杨辉三角-概述性质5，
所以$k_1 = 1, k_2 = n \dots k_{n - 1} = n, k_n = 1$
继续推导式子$(1)$,代入$\lim_{dx \rightarrow 0}$, 所以所有含有$dx$的单项式都特别小，可以看成0

\[= k_2x_0^{n-1} = nx_0^{n-1}\\therefore (x_0^n)‘ = nx_0^{n - 1} \]

证(?)毕

然后还有很多公式……
设$u, v$都是关于$x$的函数

\[(u\pm v)‘ = u‘ \pm v‘\(uv)‘ = u‘v + uv‘\(\frac{u}{v})‘ = \frac{u‘v + uv‘}{v^2} \]

证明：

\[(u(x_0) \pm v(x_0))‘ = \frac{u(x) + v(x) - u(x_0) - v(x_0)}{dx} = \frac{u(x) - u(x_0)}{dx} + \frac{v(x) - v(x_0)}{dx} = u‘(x_0) + v‘(x_0)\(u(x_0) v(x_0))‘ = \frac{u(x)v(x) - u(x_0)v(x_0)}{dx} = \frac{u(x_0 + dx)v(x_0 + dx) - u(x_0)v(x_0)}{dx} = \frac{u(x)v(x) - u(x_0)v(x_0) + u(x)v(x_0) - u(x)v(x_0)}{dx}\ = \frac{u(x)(v(x) - v(x_0)) - v(x_0)(u(x_0) - u(x))}{dx} = \frac{u(x)(v(x) - v(x_0)) + v(x_0)(u(x) - u(x_0))}{dx} = u(x)\frac{v(x) - v(x_0)}{dx} + v(x)\frac{u(x) - u(x_0)}{dx}\\ \text{由于dx太小被忽略掉了……} = u(x_0)v‘(x_0) + u‘(x_0)v(x_0)\\]

然后下一个公式也是按照定义推

\[(\frac{u(x_0)}{v(x_0)})‘ = \frac{\frac{u(x)}{v(x)} - \frac{u(x_0)}{v(x_0)}}{dx} = \frac{\frac{u(x)v(x_0) - u(x_0)v(x)}{v(x)v(x_0)}}{dx} = \frac{\frac{u(x)v(x_0) - u(x_0)v(x)}{dx}}{v(x)v(x_0)}\ = \frac{u(x)v(x_0) - u(x_0)v(x) + u(x_0)v(x_0) - u(x_0)v(x_0)}{v(x)v(x_0)dx} = \frac{(u(x) - u(x_0))v(x_0) - (v(x_0) - v(x))u(x_0)}{v(x)v(x_0)dx} = \frac{\frac{(u(x) - u(x_0))v(x_0)}{dx} + \frac{(v(x) - v(x_0))u(x_0)}{dx}}{v(x)v(x_0)}\ = \frac{u‘(x_0)v(x_0) + u(x_0)v‘(x_0)}{v(x)v(x_0)} \because dx \rightarrow 0 \therefore x \rightarrow x_0, v(x) \rightarrow v(x_0)\(\frac{u}{v})‘ = \frac{u‘v+uv‘}{v^2} \]

求导就讲到这算了吧……

约数和定理

update 20210730

百度说：

~~约数和定理在小学奥数中经常使用，在中学竞赛中也有用武之地。~~

如果一个数

\[n>0 \n=p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdot \dots \cdot p_n^{a_n} \]

其中$p_i$为质数

那么我们可以知道$n$的所有约数总共会有$(a_1+1)(a_2+1)\dots(a_n+1)$个

因为设$m$为$n$的约数的话，那么$\displaystyle m=p_1^{b_1}\cdot p_2^{b_2}\cdot \dots \cdot p_n^{b_n},0\leq b_i\leq a_i$，

所以对于每个$b_i$会有$a_i+1$个选择，我们只要随便更改一个$b_i$的取值就能得到互不相同的$m$，所以是有$(a_1+1)(a_2+1)\dots(a_n+1)$个$m$

他们分别为$p_1^0\cdot p_2^0\cdot \dots \cdot p_n^0,\quad p_1^0\cdot p_2^0\cdot \dots \cdot p_n^1,\quad p_1^0\cdot p_2^0\cdot \dots \cdot p_n^2,\quad \dots,\quad p_1^{a_1}\cdot p_2^{a_2}\cdot \dots \cdot p_n^{a_n}$

对于所有

\[p_1^0\cdot p_2^0\cdot \dots \cdot p_n^0 \p_1^0\cdot p_2^0\cdot \dots \cdot p_n^1 \p_1^0\cdot p_2^0\cdot \dots \cdot p_n^2 \\dots\p_1^0\cdot p_2^0\cdot \dots \cdot p_n^{a_n} \]

他们的和为$p_1^0\cdot p_2^0\cdot \dots \cdot p_{n-1}^0\cdot\displaystyle \sum_{j=0}^{a^n}p_n^j$

同样也会有其他一些数的和分别为$p_1^{b_1}\cdot p_2^{b_2}\cdot \dots \cdot p_{n-1}^{b_{n-1}}\cdot\displaystyle \sum_{j=0}^{a^n}p_n^j,\quad 0\leq b_i \leq a_i$

那么$n$的约数和就是$k\cdot\displaystyle \sum_{j=0}^{a^n}p_n^j$

观察一下如果$n$的约数和为$S_n$

\[S_n=\displaystyle \sum_{\forall 1\leq j \leq n,0\leq b_j\leq a_j} \left(\prod_{i=1}^n p_i^{b_i} \right) \]

那么我们的$k$

\[k=\displaystyle \sum_{\forall 1\leq j \leq n-1,0\leq b_j\leq a_j} \left(\prod_{i=1}^{n-1} p_i^{b_i} \right)=S_{n/p_n^{a^n}} \]

也就是说$S_n=S_{n/p_n^{a^n}}\cdot \displaystyle \sum_{j=0}^{a^n}p_n^j$

同理我们可以递归回去，边界条件我们可以知道$S_{p_1^{a_1}}=\displaystyle \sum_{j=0}^{a_1}p_1^j$

如果再退一下我们可以定义边界为$S_1=1$

所以最后我们就可以得到约数和定理：

\[\displaystyle n=p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdot \dots \cdot p_n^{a_n}\S_n=\sum_{j=0}^{a_1}p_1^j\cdot \sum_{j=0}^{a_2}p_2^j\cdot \sum_{j=0}^{a_3}p_3^j\dots \sum_{j=0}^{a_n}p_n^j\S_n=\prod_{i=1}^{n}\left(\sum_{j=0}^{a^i}p_i^{j}\right) \]

Lucas组合数定理

update 20210730

\[C_n^m \equiv C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\cdot C_{n\%p}^{m\%p} \mod p|p\in P \]

证：

设

\[n=sp+q,m=tp+r,\quad s,t,q,r\in \N+ \]

则

\[\forall 0<f<p,C_p^f=\frac{p!}{f!(p-f)!}=\frac{p\cdot(p-1)!}{f!(p-f)!}\equiv0\mod p \tag1 \]

再根据二次项定理

\[(1+x)^{n}=(1+x)^{sp+q}=((1+x)^p)^s\cdot (1+x)^q \(1+x)^p \equiv \displaystyle \sum_{k=0}^p C_{p}^{k}\cdot x^{p-k} y^k \equiv\sum_{k=0}^p C_{p}^{k}\cdot x^{k} y^{p-k} \mod p \]

然后根据式子(1)只有当$k=0\or k=p$的时候，才会有$p \not |C_p^k$,否则$C_p^k \equiv 0\mod p$

\[\therefore (1+x)^p \equiv 1^p+x^p =1+x^p \mod p \\therefore ((1+x)^p)^s\cdot(1+x)^q \equiv (1+x^p)^s\cdot(1+x)^q \mod p \]

然后再把$(1+x^p)^s$和$(1+x)^q$用二次项定理拆出来

\[\displaystyle (1+x^p)^s\cdot(1+x)^q \equiv \left(\sum_{i=0}^{s}C_s^i\cdot 1^{s-i}\cdot {x^p}^i\right)\cdot \left(\sum_{j=0}^{q}C_q^j\cdot 1^{q-j}\cdot x^j\right)\(1+x^p)^s\cdot(1+x)^q \equiv \left(\sum_{i=0}^{s}C_s^i\cdot {x^p}^i\right)\cdot \left(\sum_{j=0}^{q}C_q^j\cdot x^j\right) \mod p \]

继续根据二次项定理，$(1+x)^{n=sp+q}$展开之后含有$x^{tp+r}$ 的项的就是$\displaystyle C_{n}^{tp+r}x^{tp+r}$,这项在等号左边的系数就是$C_{sp+q}^{tp+r}$

我们又知道$\displaystyle (1+x)^{sp+q}\equiv(1+x^p)^s\cdot(1+x)^q \equiv \left(\sum_{i=0}^{s}C_s^i\cdot {x^p}^i\right)\cdot \left(\sum_{j=0}^{q}C_q^j\cdot x^j\right) \mod p$

我们可以根据定义知道$r,q<p$,所以$\displaystyle \left(\sum_{i=0}^{s}C_si\cdot {x^p}i\right)\cdot
\left(\sum_{j=0}^{q}C_qj\cdot x^j\right) \mod p $里面含有$x^{{tp+r}$的项一定是$i=t$的时候才能凑出来$x}{tp}$,还剩下一个$x^{r$,就是$j=r$的时候，就可以得到$x}{tp+r}$,这个时候他**在等号右边**的系数就是$i=t,j=r$对应的前面组合数$C_s^t \cdot C_q^{r$，所以我们就可以得到$C_{sp+q}}{tp+r}=C_s^t\cdot C_q^r$

再参考上面定义，$n=sp+q,m=tp+r,$我们就可以推出

\[C_n^m \equiv C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\cdot C_{n\%p}^{m\%p} \mod p|p\in P \]

在代码中，如果$\lfloor n/p \rfloor,\lfloor m/p \rfloor$仍然比$p$大，我们就可以考虑继续执行上面公式

OIer的数学基础（持续更新中）

码农公寓

0. 前言

求导

约数和定理

Lucas组合数定理

相关文章