算法与数据结构学习——数论专题

数论专题复习

前一部分来源于网络Wannafly Winter Camp冬令营

Day1 数论专题 Tangjz

整除理论

约数(因数)和倍数的定义。

以及:整除关系的传递性,约数的倍数的线性组合仍为倍数,整除关系为偏序关系反对称推出相等。

模意义下容易忽略0的问题。

质数和合数的定义:
对于$\forall n \in Z$,如果$\exists_{k \in Z, k \neq1, k \neq n} k \mid n$ 则$n$ 为合数,否则为质数

一些性质

若 $n \in Z^{+}$,则$min_{k \mid n} k \le \sqrt{n}$

对于$\forall n \in Z^{+}$,存在唯一的指数分解$n = \prod_{i=1}^{n}p_i^{e_i}$,这里$p_i$互不相同

令$\pi(n)$表示不超过$n$的质数个数,有$\pi(n)=\Theta(\frac{n}{\ln{n}})$

给出n可以知道比n小质数个数的渐近界

例:2017CCPC合肥网络赛
人从S,S+1,S+2,S+3…S+n-
作为1,2,3,4,5,6….n

贪心结论:n>S的部分 都会按j=i座(这时候最优)。然后根据质数密度判断是否有两个质数,然后暴力匹配??

继续整除理论

公约数

对于 $x_1 , x_2 , \cdots , x_n \in Z$ ,且 $\forall_{i=1,2,\cdots,n} d\mid X_i$,则称 $d$ 为它们的公约数

当$x_1,x_2,\cdots,x_n$不全为零,存在最大的公约数,称为$\gcd(x_1,x_2,\cdots,x_n)$

当$\gcd(x_1,x_2,\cdots,x_n) = 1$,称$x_1,x_2,\cdots,x_n$互质(互素),注意这里说是整体互质而不是说两两互质。是个大坑。

$\gcd(a,b) = \gcd(a,b-a) = \gcd(a,b \mod a)$

欧几里得算法:辗转相除

时间复杂度分析:$O(\log a+ \log b)$

公倍数

同余理论

不定方程

之前有课件

有理逼近

数论是整数方面的研究,有些地方将无理数用无穷级数+有理数表示。

数论函数

使用迪利克雷卷积(暑假课程)进行推导