Miller_Rabin 判断素数
如果有 \(a^{p-1} \equiv 1(\bmod p)\) ，\(p\) 大概率为质数。但是人们发现有些合数无法被这个式子判掉。
有一个显然成立的式子：
\(x^2 \equiv 1 (\bmod p) \rightarrow x^2-1\equiv 0 \rightarrow (x-1)(x+1) \equiv 0\)
当 \(p\) 是质数时，\(x\) 必定等于 \(\pm1\) ；但是如果 \(p\) 是合数，可能 \((x-1)\) 和 \((x + 1)\) 刚好就是 \(p\) 的两个因子。
当 p 是偶数并且不为 2 时，\(a^{p-1} - 1= (a^{\frac {p-1}2}-1)(a^{\frac {p-1}2} + 1)\)，于是可以追加一则对 \(p\) 是否是素数的判定，就是如果分解出来的两个因式不为零，但是乘积为零，就证明 \(p\) 是合数。如果任何一个因式为零，就不得不认为 \(p\) 是素数。然后如果 \(\frac{p-1}2\) 还是偶数，就继续分解因式，然后用上述方式判定。
实现的时候，是先用 \(p\) 的二进制，快速找到能分解出来的最小的 \(a^{\frac{p-1}k}\) ，然后再一步一步乘上去验证。
多这一个步骤竟然可以大大提升判定准确度！并且只需要 \(2,7,61\) 这几个数字就可以判定 int 内数字，用 \(2, 325, 9375, 28178, 450775, 9780504, 1795265022\) 这些数字就可以 \(100\%\) 准确判定 long long 内的数字。
Pollard Rho分解最大质因数算法
Pollard Rho算法分解一个数n的过程大体上是这样子的：
- 找到一个 \(n\) 的因子 \(p\)，将 n 分解为 p 与 n/p
- 如果p或n/p不为质数，将其带入递归上述过程
- 如果其是质数，将其记录并退出
找p的过程是这个样子：
- 找到一个数 \(p1\)
- 通过某种玄学推导手段找出一个与 \(p1\) 对应的 \(p2\)
- 如果 \(\gcd(\mid p1-p2\mid,n)\) 不是 1 或 n 时，此数为所求的 p
玄学推导手段：
\(p2 \equiv (p1^2 + c) \bmod n\)
其中c为随机常数。
出现循环了怎么办？换一个随机常数 c 再搞。
判环用 floyd判圈算法 搞定。
模板，例题
Floyd判圈算法
作用：
- 判断链表是否有环
- 计算环的长度
- 寻找环的起点
实现：
快慢指针：定义两个指针，慢指针（slow）每次前进一步，快指针（fast）每次前进两步，这里只要 fast 比 slow 前进的快即可，但前进步长太多代码会变慢，所以采用两倍于 slow 步长。
- 若无环，fast先走到终点；若有环，最终 slow 和 fast 相遇，且 fast 恰好比 slow 多走了一圈（每次fast与slow的相对位移为1，走完一圈，fast刚好多走一圈）
- 因此循环的结束条件为要么 fast 先跑到终点，要么 fast 追上 slow
- 初始化slow=head，fast=head.next，是因为如果fast初始化为head，那循环的第一个条件slow!=fast永远都不成立
while (slow != fast && fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}