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

数论定理杂烩

一个我曾搞错的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}
$$

费马小定理

条件:质数p,gcd(a,p)=1
结果:$a^{p-1}=1 (\mod p)$
顺便提一下,如果使用 $a^p=a (\mod p)$ 的形式,不需要满足gcd(a,p)=1
证明:不会
应用:
1.求逆元:【OI之路】11更高级数论-2逆元
2.某些数据范围巨大的题目如
Gauss Fibonacci
矩阵游戏

欧拉定理

欧拉定理: 当gcd(a,m)=1,$a^{\varphi(m)}=1 (\mod m)$

拓展欧拉定理:
yww
sam张
maijing
例题:BZOJ3884 bzoj4869

威尔逊定理

万一派得上用场?已经用上了,atcTenka1-2019E
当p是质数
$(p-2)! = 1 (\mod p)$

二项式定理

$$
(a+b)^n=
\sum_{i=0}^n
C_n^i \times
a^i \times
b^{n-i}
$$
深入运用

牛顿广义二项式定理,将k拓展到实数域
条件: $0 \leq |a| \le |b|$
$(a+b)^k=\sum_{i=0}^\infty {k \choose i} a^i b^{k-i}$
其中组合数定义的柿子是不变的,但不能用阶乘这个符号了
显然这个广义是兼容狭义的

神仙欧拉的另一个公式

本公式属于拓扑学的研究范围
不过之前做一道叫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$

特征方程

应用不是太广
rxz
dh

gcd的奇妙定理

只放定理,证明在这里这里
$gcd(x^a-1,x^b-1)=x^{gcd(x,y)}-1$
$gcd(fib(a),fib(b))=fib(gcd(a,b))$

斐波那契数列

$f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)$
$S(n)=f(n+2)-1$ ,可用归纳法证明

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