1. $1$既不是质数也不是和数

=> 因为所有的整数被分解质因子的结果都是唯一的, 如果$1$也是质数, 那么分解质因子的结果就不唯一(可以无限乘1)

即用质数乘法可以构造任何的数, 并且要求这个数能够被唯一表示

2. % 运算可以与 + × - 有结合律/交换律, 与除法没有该性质 (需要用到求逆元的方法)

3. 只要知道前三项就能知道是等差还是等比数列 (只有q = 1 && d = 0 才可能既是等差又是等比)

4. 质数与约数的个数:

1~N中质数的个数大约为: $N/\ln_{}{N}$
一个数N的约数个数上界为 2 × $\sqrt{N}$
1~N中所有数的约数个数总和大约为 $N/\log_{}{N}$

5. 当单独求每一个的约数时 如果复杂度过高的话, 那么就反向处理, 寻找一个数是哪些数的倍数 => 时间复杂度能够从O(nsqrt(n)) 优化至 O(nlogn)

6. 关于反质数:

引理1: 1~N中的最大反质数一定是约数个数最多中最小的一个数 => 如果不是最小的一个, 后面的数不能称之为反质数(前面存在约数个数相等的数)

引理2: 分解质因子中的质数不会超过9个 (N <= $2^{31}$-1)

引理3: 指数之和不会超过30, 并且单调递减
练习题

7.关于欧拉函数

1.规定 $\alpha(1) = 1$, 道理同1, 需要满足欧拉函数的一些其他性质, 例如积性函数…
2.求两个数互质的数对个数是线性筛求欧拉函数的一个具体用法 可参考:可见的点

8.将$n$拆分为最大的积

也就是不断将 n 拆分为多个3相乘, 2的次数不超过 3个, 这些2与3就能构成最大的乘积

9.关于同余理论

都知道, 加减乘 具有同余定理的性质 => 也就是 $a \equiv b \pmod{p}$ = $a - b \equiv 0 \pmod{p}$. 证明也不太会, 但是除法就没有这种性质( 因为除法的中间过程不一定能够整除 )

因此如果存在除法取模, 应该对它进行转化 => 变成乘法(利用乘法逆元转化).
乘法逆元: 若 a 与 p 互质, 那么根据欧拉定理就能得到 ${a^{\alpha (p)} \equiv 1 \pmod{p}}$,
若进一步, p是质数的话, 那么p的欧拉函数 = p-1, 因此就有 $a\times a^{p-2} \equiv 1 \pmod{p}$, 因此 a 的乘法逆元就是 $a^{p-2}$ => 就能够将 $b/a % p$ 转化为 $b×a^{p-2} % p$

10. 最大公约数与最小公倍数的推导

数论中关于最大公约数与最小公倍数的简单推导：
要求 a 与 b的最大公约数, 将a 与 b进行质因数分解, 其中最大公约数一定是每一个质数的两者共有的最小指数组合在一起 , 例如 $2^3 × 3^2 与 2^2 × 3^3$, 他们的最大公约数就是 $2^2 × 3^2$
所以这里有一个性质:$a/gcd(a,b) 与 b/gcd(a, b)$互质
并且同样能够推出最大公倍数的公式 = $lcm(a, b) = a*b/gcd(a,b)$

求多个数的最大公倍数:

两个数$a, b$ 的最大公倍数 = $a × b / gcd(a, b)$,
多个数的最大公倍数 = $a × b / gcd(a, b) × c / gcd(a, b, c) …$

11.同余方程

关于为什么一定要找到 a 与 b 互质的情况呢?
=> 原方程: $ax \equiv d \pmod{b}$, => ax = d + kb, 因此当求出一个 X0 特解之后, 通解就一定是关于 %b 下的解.
为了让通解能够取到所有的情况, 一定要满足 a 与 b 在互质的情况下取k的值.
因为若答案为 1, 3, 5, 7. 如果a 与 b 不互质的话(假设存在公约数2), 那么 x 取的所有解就为 1 5 9. 会漏掉很多的解!!!

12.快速判断一个数能被哪些数整除

13.欧拉定理 与 费马小定理(求逆元的)的证明

欧拉定理 : 若 $a$ 与 $n$ 互质, 那么 $a^\alpha (n) \equiv 1 mod(n)$
设 $n$ 的简化剩余系为 $x1, x2, x3 …$, 因为 $a$ 与 $n$ 互质, 所以 $ax1, ax2, ....$ 在 mod n 的意义下也是 $n$ 的简化剩余系(并且所有的数都是相等的), 可写为: $ax1×ax2×… \equiv x1×x2×…(mod n)$, 化简得 $a^\alpha (n) \equiv 1 (mod n)$

费马小定理在此基础上添加了一个 $n$ 为 质数的条件, 所以 $a^{-2}$ 是 $a % n$ 的逆元