526互联

初等数学瞎扯Ⅱ：辅助工具

发布时间 2023-04-25 14:09:27作者: -Comρℓex-

0. 前置知识

1. 乘方运算

1-0. 问题简述

求 \(b^m\pmod p\)。

1-1. 普通快速幂

快速求 \(a^b\pmod p\)

朴素算法是 \(O(b)\) 的，考虑优化这一过程。

设 \(b\) 在二进制意义下的第 \(i\) 位值为 \(w_i\)，则答案为 \(\prod_{2^i\leq b}a^{2^iw_i}\)。由于 \(w_i=\{0,1\}\)，求出 \(a^{2^i}\) 即可，复杂度 \(O(\log b)\)。

typedef long long ll;
ll qp(ll a,ll b,ll p){
	ll res=0;
	for(;m;m>>=1){if(m&1)res=res*a%p;a=a*a%p;}
	return res;
}

1-2. 光速幂

适用于 \(a\) 不变，\(b\) 较小，询问较多的情况。

我们令 \(b=xm+q\)，其中 \(q<x\)，则 \(a^b=a^{xm}\times a^q\)，预处理 \(a^{xm}\) 和 \(a^q\) 即可 \(O(1)\) 回答。

注意到预处理部分复杂度是 \(O(\frac{b}{x}+x)\) 的，由欧拉定理可知，\(b\leq \varphi(p)\)，由于 \(p\) 一般是质数，这里令 \(\varphi(p)\) 与 \(p\) 同阶，根号平衡取 \(x=\sqrt p\) 即可。

typedef long long ll;
ll pw[P][2];
void init(ll a,ll p){
	ll f=sqrt(p);
	for(int i=pw[0][0]=1;i<=f;i++)pw[i][0]=pw[i-1][0]*a%p;
	for(int i=pw[0][1]=1;i<=p/f;i++)pw[i][1]=pw[i-1][1]*pw[f][0]%p;
}
ll qp(ll a,ll b,ll p){
	ll f=sqrt(p)
	return pw[b/f][1]*pw[b%f][0]%p;
}

2. 素性检验与质因数分解

2-0. 问题简述

判定一个数 \(n\) 是不是素数，若不是，对其分解质因数。

2-1. 素性检验

2-1-1. 试除法

即枚举 \(2\) 到 \(n-1\) 的所有数字 \(i\)，判断是否有 \(n\equiv 0\pmod i\) 即可，复杂度 \(O(n)\)。

2-1-2. 优化的试除法

上面的做法看起来非常呆，我们考虑优化这一过程。

首先给出定理

若 \(n\) 为合数，则其最小素因子 \(p\) 一定不大于 \(\sqrt n\)。

证明：反证，若其最小素因子 \(p\) 大于 \(\sqrt n\)，令 \(d=\frac{n}{p}\)，则 \(d<\sqrt n\)，且 \(d\) 的最小素因子 \(p'\) 一定满足 \(p'\leq d< \sqrt n<p\)，且为 \(n\) 的一个不为 \(p\) 的素因子，与原假设矛盾，故其小于 \(n\)。

也可以考虑另一种证明，若最小素因子 \(p\) 也是最小因子，则 \(\frac{n}{p}\) 一定大于 \(p\)，即要在大于 \(\sqrt n\) 的数中找到两个数使其乘积等于 \(n\)，显然不成立，而第一个命题也是显然的，若 \(p\) 不是最小因子，设其有更小的因子 \(d\)，则 \(d\) 的最小素因子一定小于 \(p\)，与 \(p\) 为最小素因子矛盾。

那我们直接在 \(\sqrt n\) 范围内枚举即可，复杂度 \(O(\sqrt n)\)。

2-1-3. Miller-Rabin 算法

2-1-3-1. Miller-Rabin 算法思想

上述的算法效率太低，我们考察一个更高效的算法。

首先用到费马小定理，可以参见初等数学瞎扯Ⅰ：同余相关1-1。

若 \(p\) 为质数，\(a\bot p\)，则 \(a^{p-1}\equiv1\pmod p\)。

我们写出其逆反命题

若 \(a\bot p,a^{p-1}\not\equiv1\pmod p\)，则 \(p\) 不是质数。

那么我们可以取一组 \(a\)，检查 \(a^{p-1}\) 模 \(p\) 的值即可。这样大概率是对的。

但是这并不等价于若 \(a^{p-1}\equiv1\pmod p\)，则 \(p\) 是质数。对于一些合数，有部分数字的 \(p-1\) 次方模 \(p\) 为 \(1\)，比如 \(2^{340}\equiv 1\pmod {341}\)。

然后可以考虑多随机几组 \(a\)，这样能排除大量的上述情况。

但是这并不等价于对于若干个 \(a\) 若 \(a^{p-1}\equiv1\pmod p\)，则 \(p\) 是质数。

对于一类卡迈尔数，它满足对于所有 \(a\bot p\)，\(a^p\equiv 1\pmod p\)，比如 \(561\)。

所以单上费马小定理是肯定不行的，接下来需要二次探测定理。

若 \(p\) 为质数，则 \(x^2\equiv 1\pmod p\) 有且仅有解 \(\pm 1\)。

同理写出逆反命题

若 \(x^2\equiv 1\pmod p\) 的解不只有 \(\pm 1\) ，则 \(p\) 不为质数。

具体证明在二次剩余里提到，关于二次剩余的知识可以参见初等数学瞎扯Ⅰ：同余相关二次剩余。

我们不妨令 \(p-1=r\times2^d\)，则我们根据二次探测定理，当 \(a^{p-1}\equiv1\pmod p\) 时，若 \(p-1\) 是 2 的倍数，则 \(a^{\frac{p-1}{2}}\equiv 1\pmod p\) 的解必须是 \(\pm1\)。以此类推，并重复 \(d\) 轮即可。

将这两种做法结合起来后，我们可以发现此时对合数误判的概率相当低，同时我们可以随机多组数据，以保证正确性。

Miller-Rabin 算法的复杂度与随机次数息息相关，若我们把单次乘法的复杂度记为 \(O(1)\)，则 Miller-Rabin 算法的复杂度为 \(O(k\log^2 n)\)，其中 \(k\) 是随机轮数。

但对于 OI 而言，Miller-Rabin 算法是可被视作确定性算法的，具体原因是我们要判断的数一般值域在 \([0,2^{64})\) 次方内，而对于这个范围内的数字，已经被证明了可以用一组固定的 \(a\) 完成全部检测，具体可以参见wangrx的博客：论 Miller-Rabin 算法的确定性化，这里给出结论。

对于 \(2^{32}\) 内的数字检测，使用 \(2,7,61\) 即可。

对于 \(2^{64}\) 内的数字检测，使用 \(2,325,9375,28178,450775,9780504,1795265022\) 即可，但这种抽象东西我们一般不会去背，所以使用前 \(10\) 个质数即可完成检测。

关于更详细的信息，可以参见 OEIS。

朴素实现的复杂度是 \(O(kd\log n)\) 的，视 \(d\) 与 \(\log n\) 同阶，复杂度为 \(O(k\log^2 n)\)。

注意到其实仍有优化空间，复杂度瓶颈在二次探测。我们考虑把二次探测的过程翻过来，把 \(d\times 2^r\rightarrow d\) 变为 \(d\rightarrow d\times 2^r\)，我们只需要算出 \(a^d\)，然后平方 \(r\) 次即可。复杂度 \(O(k\log n)\)。当然你也可以搞光速幂，单次快速幂的复杂度降低为常数，但是这不是复杂度瓶颈，故略去。

注意 \(p\) 无法通过以 \(p\) 为底的素性检验，所以你需要特判底数。

2-1-3-2. Miller-Rabin 代码实现

ll prime_list[10]={2,3,5,11,17,19,23,37,41,43};
ll qp(ll b,ll m,ll p){
	ll res=1;
	for(;m;m>>=1,b=b*b%p)if(m&1)res=res*b%p;
	return res;
}
bool miller_rabin(ll n,ll a){
	ll d=n-1,r=0;while(!(d&1))d>>=1,r++;
	ll x=qp(a,d,n);if(x==1)return 1;
	for(int i=0;i<r;i++){if(x==n-1)return 1;x=x*x%n;}
	return 0;
}
bool prime(ll n){
	if(n<2)return 0;
	for(int _=0;_<10;_++){
		if(n==prime_list[_])return 1;
		if(!miller_rabin(n,prime_list[_]))return 0;
	}return 1;
}