【OI之路】03数学-2定理杂烩

定理杂烩

模意义的定理放在模意义数域一章了

秦九韶算法(霍纳法则)

$2x^3+4x^2+3x+1=((2*x+4)*x+3)*x+1$,即线性求值

约数个数与和

$G=p1^{a1}\times p2^{a2}\times p3^{a3}\times …\times pk^{ak}$
$约数个数=(a₁+1)(a₂+1)(a₃+1)…(ak+1)$
$和=(p1^0+p1^1+…p1^{a1})(p2^0+p2^1+…p2^{a2})…(pk^0+pk^1+…pk^{ak})$
其实就是乘法原理

神仙欧拉的另一个公式

本公式属于拓扑学的研究范围
不过之前做一道叫planar的题目用到过
对于一个平面图,一定满足$m \leq 3n-6$

原公式:点数n+面数r-边数m=连通块数量cnt(当做无向图)+1
对于当前的平面图判定,每条边最多给两个面使用,每个面至少有3条边
也就是说,$r \leq \frac{2m}{3}$
原式化为 $m=n+r-cnt-1$ 后带入,得到 $m \leq n+\frac{2}{3} m -cnt-1$
$3m \leq 3n+2m-3cnt-3$
显然cnt最小为1,则 $m \leq 3n-6$

特征方程

rxzdh

gcd的奇妙定理

$gcd(a^m-b^m,a^n-b^n)=a^{gcd(n,m)}-b^{gcd(n,m)}$,证明
$gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1$,证明在这里这里例题 HDU5780

斐波那契数列

$$
F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)=\frac{\sqrt 5}{5}((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n) \\
\sum_{i=1}^n F(i)=F(n+2)-1、
\sum_{i=1}^n F(i)^2=F(n)F(n+1) \\
\sum_{i=1}^n iF(i)=nF(n+2)-F(n+3)+2 \\
\sum_{i=1}^n F(2i-1)=F(2n),\sum_{i=1}^n F(2i)=F(2n+1)-1 \\
$$
证明


$$
A. gcd(F(i),F(i+1))=gcd(F(i),F(i-1))=gcd(F(0),F(1))=1 \\
B. 考虑fib(n)的组合意义:用1*2的骨牌填充2*(n-1)的表格方案数 \\
考虑n与n+1间是否断开,F(n+m)=F(n)F(m-1)+F(n+1)F(m) \\
C. gcd(F(n+m),F(n))=gcd(F(m-1)F(n)+F(m)F(n+1),F(n))=gcd(F(m),F(n)) \\
仔细观察发现fib的下标也在辗转相减,gcd(F(n),F(m))=F(gcd(n,m)) \\
$$

于是我们做个练习(例题:最小公倍佩尔数):

佩尔数$P(n)=2P(n-1)+P(n-2)$,首先A是一样的,然后B是竖着放有两种方案,但式子是一样的,故C也一样

差分表

教程1教程2教程3
$$
设当前有n次多项式f,设\Delta_0 f(x)=f(x),\Delta_{t+1} f(x)=\Delta_t f(x)-\Delta_t f(x-1) \\
那么我们称f的第0条对角线为\Delta_0 f(0)…\Delta_n f(0) \\
牛顿插值:f(x)=\sum_{k=0}^n \Delta_k f(0) C_x^k \\
根据组合数的性质,可知\sum_{k=0}^m f(k)=\sum_{k=0}^n \Delta_k f(0) C_{m+1}^k
$$
题目:cf407c

Kummer定理

$$
p在n!中次数=\sum_{i=1} \lfloor n/p^i \rfloor
=\sum_{i=1}\sum_{j=i}c_jp^{j-i}
=\sum_{j=1}c_j\sum_{i=1}^jp^{j-i} \\
=\sum_{j=1}c_j\sum_{i=0}^{j-1} p^i
=\sum_{j=1}c_j \frac{p^j-1}{p-1}
=\frac{(n-c_0)-\sum_{j=1} c_j}{p-1}=\frac{n-sc(n)}{p-1} \\
p在C_{n+m}^n中次数=\frac{sc(n)+sc(m)-sc(n+m)}{p-1}=n+m在p进制下进位个数
$$

这个定理的形式和意义都很优美;例题:GDOI2019D2T1

其他知识

  1. 通过$O(\sqrt n)$枚举出n的所有约数
    推论: n的约数总数,上限$2 \sqrt n$

  2. 通过$O(n log_2 n)$枚举d,更新其倍数得到1~n的所有约数
    复杂度证明:调和级数
    推论:1~n的所有约数个数,上限$n log_2 n$

  3. 对于int范围内的x,其质因子数量<10
    证明就是把最小那几个乘起来,然后指数总和<31

  4. 素数分布数量,n内大致上看作$n/ln n$

  5. 一个我曾搞错的trick: $\forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$

    略证:

$$
\begin{split}
&\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\ \Rightarrow \\ &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\
\end{split}
$$

  1. phi小性质A:对于n>1,1~n中与n互质的数的和为$n \times \varphi(n)/2$ ,证明:$gcd(n,x)=gcd(n,n-x)$
  2. phi小性质B:深度为log级别。考虑n为偶数,则$\varphi(n)\le n/2$;若n为奇数,$\varphi(n)$一定是偶数

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/a06a.html
转载请注明出处,谢谢!