由于篇幅有限，下面有时会不加证明地给出问题的结论，详细的推论请看《算法导论》31章
1. 最大公约数
实现代码传送门
1.1. 性质
如果d为非0整数a的约数且同时为非0整数b的约数，则称d是a和b的公约数，如果d是所有公约数中最大的一个，则称其为a和b的最大公约数（Greatest Common Divisor, gcd），记为 \(d=\gcd(a,b)\)
下面是 \[ \begin{array}{ll} \gcd(a,b)=\gcd(b,a) \\ \gcd(a,b)=\gcd(-a,b) \\ \gcd(a,b)=\gcd(|a|,|b|) \\ \gcd(a,0)=|a| \\ \gcd(a,ka)=|a| \end{array} \]
1.2. 分解质因数法
如果一个数a可以被一个质数p整除，则称p为a的一个质因数。如果p同时为a和b的质因数，则p也为a和b的公约数，且p一定可以被a和b的最大公约数整除。
故，只要不断地对a和b进行分解出相同的质因数，直到不能继续分解出相同的质因数为止，则所有分解出来的质因数的乘积d即为a和b的最大公约数。
只适用于较小的数，但对于数论研究的数，一般都为较大的数，这种方法不仅耗时，而且如何确认两个整数是否已经不能继续分解出相同质因数，也是一个相当困难的事情。
1.3. 辗转相除法
也称欧几里得法，利用到如下性质 \[ \gcd(a,b)=\gcd(b,a \bmod b) \] 其中，\(a>b>0\)
该方法通过不断进行上述运算，直到左式中的 \(b=0\)，则最大公约数为 \(a\)
1.4. 更相减损法
《九章算术》里记载的求最大公约数的方法，利用到如下性质 \[ \gcd(a,b) = \gcd(b,a-b) \] 其中，\(a>b>0\)
该方法通过不断进行上述运算，直到左式中的 \(b=0\)，则最大公约数为 \(a\)
其实，更相减损法和辗转相除法本质上是一样的，只是前者用减法去实现后者的求模运算
1.5. stein算法
在处理两个较大的质数时，辗转相除法的计算资源会消耗很大，为此，提出了Stein算法，通过只进行整数的移位和加减法，可以大大节省计算资源。
首先，我们得有有这样一个认识，计算机处理乘或除2的自然次数幂比乘除其他值更加节省资源，例如乘2就相当于其二进制数右移一位，除2相当于其二进制数左移一位。另外，计算机处理加减法比处理乘除法节省资源。这与上面两个原理，下面给出具体流程：
- 初始化一个公共质因数积缓存变量 \(c=1\)
- 如果 \(a\) 和 \(b\) 都是偶数，则 \(a=a/2,b=b/2,c=2c\)。这一步的意思就是2是a和b的公共质因数，那就把2缓存下来，同时把a和b缩小一倍。
- 如果 \(a\) 和 \(b\) 都不是偶数，则 \((a,b)=(|a-b|,\min(a,b))\)。这一步其实就是更相减损法的步骤了。
- 如果 \(a\) 是偶数，\(b\) 不是偶数，则 \(a=a/2\)。这一步说明2一定不是a和b的公共质因数，所以可以大胆的将a缩小一倍，这不会对最终结果产生任何影响。
- 如果 \(b\) 是偶数，\(a\) 不是偶数，则 \(b=b/2\)
- 如果 \(a=0\)，则最大公约数为b和c的积，算法结束；如果\(b=0\)，则最大公约数是a和c的积，算法结束；否则，重复步骤2~6
stein算法本质上是分解质因数法和更相减损法的结合体，其通过不断缩小a和b的规模，渐进地求取a和b的最大公约数。
1.6. 扩展的欧几里得算法
为了解决一些特殊问题，例如：求解模线性方程及方程组、计算模逆元等问题，可以重写欧几里得算法的表现形式已扩展其使用范围。
对于存在最大公约数的整数a和b，必然存在整数x和y，使其满足下面条件 \[ d=\gcd(a,b)=ax+by \] 扩展的欧几里得算法一个满足式的三元组 \((d,x,y)\)，其具有以下性质 \[ (d,x,y)=(d,y,x- \lfloor a/b \rfloor y) \] 该方法求最大公因数的步骤和朴素的欧几里得法是一样，只是每个步骤中都要进行一次上述的变换
1.7. 多个整数的最大公约数
对于输入的数组，进行如下步骤：
- 对这数组进行降序（从大到小）排序
- 依次对相邻的两个数进行如下操作：设相邻的两个数为\(a\)和\(b\)，如果 \(b \neq 0\)，则令 \(a = a \bmod b\)，否则，令 \(a=a\)
- 重复步骤1~2，直到数组中只有一个数不为0，则该数即为这些整数的最大公约数
1.8. 非整数的最大公约数
自然数的最大公约数的定义可以扩展至非整数。一组非整数分别除以它们的最大公约数应得一组整数，而这组的整数的最大公约数为1。
1.8.1. 分数
两个分数的最大公约数的分子为其两个分子的最大公约数，分母为其两个分母的最小公倍数，即 \[ k=\gcd(a/b,c/d)=\frac{\gcd(a,c)}{lcm(b,d)}=\frac{\gcd(a,c)}{b*d/\gcd(b,d)} \]
1.8.2. 小数
一般做法为先将小数转化为分数，在按照分数求其最大公约数。
非循环有理小数
这种类型的小数转换比较简单。
先将该小数转化为“分子是小数部分、分母是 \(10^n\) （n为小数部分的位数）”的一般分数形式，然后再求分母分子的最大公约数进行约分，即可得到该小数的分数形式。
例如，0.25 的分数形式为 \(\frac{25}{100}\)，\(\gcd(100, 25) = 25\)，分子分母约分，的分数形式为 \(\frac{1}{4}\)
循环有理小数
这种类型的小数转换也比较简单，用到原理是真•小学二年级学过的知识，具体证明略。
先区分小数部分的不循环部分和循环部分，然后转化为“分子是不循环部分和一个循环节的数字组成的数减去不循环部分的差、分母是按一个循环节的位数写n个9以及再在后面按不循环部分的位数添写n个0”的一般分数形式，最后再求分母分子的最大公约数进行约分，即可得到该小数的分数形式。
例如，\(0.25\dot{6}7\dot{8}\) 先转化为一般分数形式为 \(\frac{25678-25}{99900}=\frac{25653}{99900}\)，又\(\gcd(25653,99900)=3\)，分子分母约分，其分数形式为 \(\frac{8551}{33300}\)
但理论很丰满，现实很骨感。由于计算机的精度问题，计算机并不能返回循环小数。例如，当计算 \(1/7\) 时，python3返回的结果为 0.14285714285714285 。这是一个近似值，但作为程序输入时，程序就会将其当做精确值进行运算，即程序会将其作为非循环小数进行转化，最终得到分数形式并非 \(\frac{1}{7}\)。
出现这种结果也是很好理解的，因为程序会默认将所有的输入都当做非循环有理小数，除非程序默认输入的都是一个循环小数，那么一个新的问题出现了：怎样区分非循环部分和循环部分？
一个简单的方法是将浮点数转化为字符串，提取字符串重复的部分作为循环体，不重复的部分作为非循环部分。但如果循环体很长以至于程序返回值都无法完全展示其中一段循环体时，这个方法并不奏效，我们也很容易找到这样的例子，例如，\(1/17 \approx 0.058823529411764705\) 。事实上，也只有分母为质数的分数的小数形式的循环体比较长，考虑到质数的密度（见下一章的介绍），这个方法在一定的精度要求范围内还是可行的。
不循环无理数
常见的无理数如小数次幂数、圆周率 \(\pi\)、黄金分割率 \(\varphi\)、欧拉数 \(e\)、无限连分数等
这种类型比较困难，因为只能转化为一个无限接近的分数形式，至于要精确到怎样的程度才合适，暂时没看到通用的解决方案。这里暂时挖坑，以后有机会再填~
2. 模运算
实现代码传送门
2.1. 性质
2.1.1. 欧拉定理
对于大于1的整数 \(n\)，满足下式 \[ a^{f(n)} \equiv 1 \pmod n,\forall a < p \]
其中，\(a \equiv b \pmod n\) 表示 \(a\) 与 \(b\) 对模 \(n\) 同余，即 \(a \bmod n = b \mod n\)
2.1.2. 费马定理
若 \(p\) 为质数，则满足下式 \[ a^{p-1} \equiv 1 \pmod n,\forall a < p \]
另外，一般称下式为费马小定理 \[ a^p \equiv a \pmod p, \forall a < p \]
2.1.3. 非平凡平方根
如果 \(x \not \equiv \pm 1 \pmod n\) ，满足 \(x^2 \equiv 1 \pmod n\)，则称 \(x\) 为以 \(n\) 为模的1的非平凡平方根。特别地，当 \(n\) 是素数时，\(x\) 没有非平凡平方根。
2.2. 中国余数定理
对于大于1的自然数 \(N\)，其质因数序列为 \(\{n_1,n_2...n_k\}\)，对于任意整数序列 \(\{a_1,a_2...a_k\}\)，中国余数定理（又称孙子定理）用于求解下列方程组 \[ \left \{ \begin{array}{ll} x &\equiv a_1 \pmod {n_1} \\ x &\equiv a_2 \pmod {n_2} \\ &\vdots \\ x &\equiv a_k \pmod {n_k} \end{array} \right . \] 首先我们给出方程组的通解。
设 \(N_i=N/n_i\) 表示除 \(n_i\) 外其他因数的积，又设 \(t_i=N_i^{-1}\)，其中，\(t_i\) 表示 \(N_i\) 模 \(n_i\) 的数论倒数（逆元），即 \(N_it_i \equiv 1 \pmod {n_i}\)，求逆元需要用到扩展的欧几里得算法，对于 \((d,x,y)=extended-euclid(N_i,n_i)\)，我们有 \(t_i=x\)
则方程组的通解为 \[ x = bN + \sum_{i=1}^k a_it_iN_i \] 在模 \(N\) 的层面上，其特解为 \[ x = (\sum_{i=1}^k a_it_iN_i) \bmod N \]
2.3. 模取幂
模取幂运算是数论中经常出现的一种运算，质数问题大多都依赖模取幂运算。
模取幂是求一个数对另一个数的模运算，即 \(a^b \bmod n\) 的值
一般采用反复平方法进行模取幂运算。
对 \(b\) 转换成二进制模式 \(\{b_0, b_1...b_k\}\) ，我们不直接求 \(a^b\) 的值，转而渐进地求 \(b\) 的每一位模取幂的值。
初始化 \(c_{-1}=0,d_{-1}=1\) ，进行如下运算： \[ \left \{ \begin{array}{ll} c_i=2c_{i-1},d_i=d_{i-1}^2 \bmod n & b_i=0 \\ c_i=2c_{i-1} + 1,d_i=d_{i-1}^2 a\bmod n & b_i=1 \end{array} \right . \] 我么你可以看出：
如果 \(b_i=0\)，则 \(d_{i+1}=d_i^2 \bmod n = a^{c_{i+1}} \bmod n\)
如果 \(b_i = 1\)，则 \(d_{i+1}=d_i^2 a \bmod n = a^{2c_{i} + 1} \bmod n = a^{c_{i+1}} \bmod n\)
故，当 \(c_i=b\) 时，即可得到 \(a^b \bmod n\) 的值
3. 质数问题
实现代码传送门
3.1. 质数密度
质数密度的分布函数设为 \(\pi(n)\)，该值近似于 \[ \lim_{n \to \infty} \frac{\pi(n)}{n/\ln n} = 1 \]
3.2. 伪质数测试
质数测试，即检测一个非零自然数是否为质数。
根据费马定理，我们可以得到以下看似可行的质数测试方法。
现在对于输入的非零自然数 \(n\)，如果其满足下式： \[ a^{n-1} \equiv 1 \pmod{n} \] 其中，\(a\) 为任意大于1且小于 \(n-1\) 的自然数。
虽然存在 \(n\) 为合数时，仍然满足上式，此时，称 \(n\) 为一个基于 \(a\) 伪质数。但可以证明，\(n\) 仍然很大概率是一个质数。对于 \(a=2\) 的伪质数测试中，\(n<10^4\) 时，只有22个数是伪质数；\(n<10^{512}\) 时，伪质数的概率小于 \(1/10^{20}\)；\(n<10^{1024}\) 时，伪质数的概率小于 \(10^{41}\)。可以看出，这个方法的精度还是很高的。
特别地，如果一个数是基于所有的 \(a \in Z'_n = {2,3...,n-1}\) 的伪质数，则称 \(n\) 为 Carmichael 数
3.3. 质数测试
下面介绍的是一种更加靠谱的质数方法：Miller_Rabin 随机性质数测试方法。
该方法根据非平凡平方根给出一个更加靠谱的方法：
通过连续平方，在每次的平方取模后判断是否为合数
随机取多个基值 \(a\)，减少出错的概率
下面是具体的算法思想：
对于求解满足式 \[ a^{n-1} \equiv \pm 1 \pmod{n} \] 首先，令 \(n-1=2^tu\)，该式表示 \(n-1\) 的二进制表示是奇数 \(u\) 的二进制表示后面跟上 \(t\) 个零。
则 \(a^{n-1} \equiv (a^u)^{2^t} \pmod n\)，故问题转化为求解 \(a^u \bmod n\) ，再连续平方 \(t\) 次来求解 \(a^{n-1} \bmod n\)
设当前值为 \(x\) ，在平方取模 \(n\) 后，如果结果为1且 \(x\) 不为1或 \(n-1\)，则说明 \(x\) 对模 \(n\) 有非平凡平方根，则 \(n\) 一定是合数。
如果最终还是不能断定 \(n\) 是合数，只能按照费马定理判断了。
上面的结果中，仍然会出现测试错误的情况，所以，MR测试随机选取 \(s\) 个不重复的 \(a\) 进行测试，以减少出错的概率。
3.4. 质因数分解
质因数分解问题即把一个自然数分解为一个或多个质数相乘的形式。
一般不断采用Pollard的rho启发式（因为其求解过程像希腊字母 \(\rho\) ）算法来寻找输入值的一个因数，直到找到质因数为止。
该算法的思想如下：
对于求解输入值为 \(n\)的质因数，判断 \(n\) 是否为质数，如果是，则直接返回即可，否则，继续下面操作。
首先随机选取一个位于 \([0, n-1]\) 随机数 \(x\)，每次对 \(x\) 进行如下运算： \[ x = (x^2-1) \bmod n \] 缓存每2的整次数幂时刻的\(x\)，将其保存为 \(y\)，即缓存第 \(\{1,2,4...2^k\}\) 次时刻得到的 \(x\)
计算 \(y-x\) 和 \(n\) 的最大公约数 \(d\)，如果 \(d\) 不为1或 \(n\) ，说明 \(d\) 是 \(n\) 的非平凡因数（除1和自身的因数）
因为该算法是启发式，所以不保证返回的是质数，也不保证运行的效率，但可以保证的是，其返回的值一定是输入值 \(n\) 的一个因子 \(p\)，且时间复杂度小于 \(O(\sqrt{p})\)，如果 \(p\) 是合数，则时间复杂度还会小于 \(O(n^{1/4})\)
得到输入值的一个因数后，问题就变得很简单了。直接将该因数和另一个因数，递归地传入上面算法中，即可得到输入值的质因数序列。
3.5. 寻找质数
目前只找到了生成小质数的算法：埃拉托色尼筛选法（the Sieve of Eratosthenes），简称埃氏筛法。该算法非常简单。主要流程如下：
创建一个在区间 \([2,r]\) 的集合，从小到大遍历集合内的元素，每次遍历，将该元素大于1的整数倍的元素从集合中剔除。遍历完所有的元素后，集合中剩下的就是质数了。
例如，首先遍历的元素是2，则将2的倍数的元素删除；然后下一个遍历的是3，则把3的倍数的元素删除；接下遍历的是5，则把5的倍数的元素删除；……；依次类推，直到遍历最后一个元素。
可以看出，该算法本质上是暴力枚举法，是无法寻找大质数，但对于小质数的查找还是很快的。
4. references
https://blog.csdn.net/z84616995z/article/details/21945197
