数论专题复习

前一部分来源于网络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)\)

公倍数

同余理论

不定方程

之前有课件

有理逼近

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

数论函数

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