数论知识小结 [微提高篇]

Posted on 2023-08-12 Edited on 2024-04-19 In OI 笔记

数论知识小结 [微提高篇]

二次剩余和高次剩余

$y^c\equiv x\pmod P$ 则 $y$ 为 $x$ 模 $P$ 的 $c$ 次剩余。

关于二次剩余

$\mathrm{Miller\_Rabin}$ 素数检测

$x$ 是质数的必要条件是：

$\forall a,a^{x-1}\equiv 1\pmod x$。

同于对于一个质数 $x$，必然有：

$a^2\equiv 1\pmod x$ 的解只有 $1,x-1$。

证明是：

$\because a^2\equiv 1 \pmod x$

$\therefore (a-1)(a+1)\equiv 0 \pmod x$

因为 $x$ 是质数，所以 $a-1\mod x=0$ 或 $a+1\mod x=0$，即 $a\in\{1,x-1\}$。

$\mathrm{Miller\_Rabin}$算法的步骤

将 $x-1$ 分解为 $x-1=2^s\cdot t$。

找一个 $<x$ 的质数 $a$，求出 $b\equiv a^t \pmod x$。

将 $b$ 进行 $s$ 次平方，设这一次平方的结果 $b^2\equiv c \pmod x$。

当出现 $c=1$时，$b$ 只能为 $1$，$x-1$ 否则 $x$ 就不是质数。

$s$ 次平方后，$b\equiv a^{x-1}\pmod x$，若 $b\ne 1$，则 $x$ 不是质数。

在一定范围内，使用指定的极少个进行检测就能保证正确性。即便不这么做，也不需要太多的质数。模板题跑5次就能过了。

注意 $x\leq 2\or 2|x$ 要特判，取模需要快速乘。

int Miller_Rabin(ll x){
	if(x==2) return 1;
	if(x<=1 || ~x&1) return 0;
	ll s=0,t=x-1;
	while(~t&1) s++,t>>=1;
	rep(i,1,20) {
		ll a=prime[rand()%primecnt+1],b=qpow(a,t,x),c;
		rep(j,1,s) {
			c=qmul(b,b,x);
			if(c==1 && b!=1 && b!=x-1) return 0;
			b=c;
		}
		if(b!=1) return 0;
	}
	return 1;
}

可以结合 $\mathrm{Miller Rabin}$ 的 $n^{\frac{1}{3}}$ 特殊情况质因数分解

实际上，这种方法常用于求 $n$ 的因子个数

方法非常简单，先对于所有 $pri_i\le n^{\frac{1}{3}}$ 的因子对于 $n$ 筛去，剩下的部分中，所有质因子 $>n^{\frac{1}{3}}$。

因此最多包含两个质因数（可能相同）。

用 $\mathrm{Miller\_Rabin}$ 判断是否只包含一个质数，然后简单判别两个质因数是否相同即可。

复杂度为 $O(\log n+\pi (n^{\frac{1}{3}}))$。

小范围内比下面的 $\text{Pollard's\_Rho}$ 更快，更简单。

$\text{Pollard's\_Rho}$质因数分解

核心就是名字里的 Rho ( $\rho$ )，是伪循环的一个形象的表示。

伪循环：从某一个时刻开始，进入一个真循环，之前的时间就是 $\rho$ 的脚。

构造伪随机函数 $G_n(x)=(x^2+c)\mod n$。

构造数列 $a_i=G_n(a_{i-1})$。

由于函数的值域只有 $[0,n-1]$，必然出现伪循环，即在从个位置开始，进入一个未知长度的循环，也就是长成了一个 $\rho$ 的形状。

由于这个函数是伪随机函数，所以这个循环大小在期望情况下是 $O(\sqrt n)$ 的。

$\text{Pollard's\_Rho}$ 算法要找到一个 $p\in[2,n-2],p|n$。

考虑用 $\text{Floyd}$ 算法找环，即定义两个变量，一个每次走一步，一个每次走两步，设他们为 $x,y$。

当 $x=y$ 时，显然出现循环。

由于 $p|n$，所以当 $x \equiv y \pmod p$ 时，实际上是 $G_p(x)$ 这个函数出现了循环。

所以在找 $G_n(x)$ 的循环时，可以通过求出 $\gcd(x-y,n)$ 判断是否出现$G_p(x)$ 的循环。

注意如果出现 $x=y$ 情况已经找到 $n$ 的循环，说明这个我们这次构造的这个函数找不到 $p$ 的循环。

由于 $\forall n\notin prime,\exist p\in[1,\sqrt n],p|n$。

所以期望情况下每 $\sqrt p\leq \sqrt {\sqrt n}=n^{\frac{1}{4}}$ 的长度会出现循环。

算法复杂度是期望 $O(n^{\frac{1}{4}}\log n)$ 的。

那么写出 $\text{Pollard's\_Rho}$ 算法的代码。

ll Pollards_Rho(ll n){
	ll c=rand(); // 随机生成一个函数
    ll x=rand(),y=x,d=1; // 随机一个初始值
    while(d==1){
		x=(qmul(x,x)+c)%n;
		y=(qmul(y,y)+c)%n;
		y=(qmul(y,y)+c)%n;
		d=gcd(n,abs(x-y));
	}
    if(d==n) return Pollards_Rho(n); // 构造失败
    else return d; // 找到了p
}

不断调用即可完成对于n的质因数分解

对于质因数分解，更高级的算法可以参考LOJ-6466

莫比乌斯函数

设 $n=\prod_1^m p_i^{c_i}$，其中 $c_i>0,p_i$ 为质数。

则莫比乌斯函数 $\mu(n)=\left\{\begin{aligned}1 && n=1\\ (-1)^m && \nexists c_i>1 \\ 0 && \exists c_i>1\end{aligned}\right.$。

狄利克雷卷积

对于数列 $F,G$，他们的狄利克雷卷积（下记作 $F\oplus G$ ）为:

\[ (F\oplus G)_i=\sum_{d|i}F_d\cdot G_{\frac{i}{d}} \] \[ \ \]

莫比乌斯反演

设元函数 $E_i=1$，$G=F\oplus E$，即 $G_i=\sum_{d|i}F_d$.

由 $G$ 反解 $F$ 得到莫比乌斯反演 $F_i=\sum_{d|i}\mu(d) G_{\frac{i}{d}}$。

积性函数

积性函数的定义，对于一个定义在 $\Z$ 上的函数$ F(n)$，若满足

$F(1)=1,\forall (u,v)=1,F(u)\cdot F(v)=F(u\cdot v)$，则 $F(u)$ 是一个积性函数

完全积性函数对于任意的 $u,v$ 对满足上述性质

常见的积性函数有

元函数 $e(n)=[n=1]$。
因数个数函数 $d(n)$。
欧拉函数 $\varphi(n)$。
莫比乌斯系数 $\mu(n)$。
约数和函数 $\sigma(n)$。

推论：任意两个积性函数的狄利克雷函数卷积仍然是积性函数。

线性筛筛法求解积性函数

把积性函数 $F(n)$ 表示为：

$F(n)=\left\{\begin{aligned} 1 && n=1 \\ G(n) && n=p_i^t \\ \prod G(p_i^{c_i}) && n=\prod p_i^{c_i}\end{aligned}\right.$

如果能在较短的时间内求得 $G(p_i^t)$，则可以用线性筛法求解积性函数 $F(n)$ 的前 $n$ 项。

一个最简单的应用: 在 $O(n)$ 时间求解 $id^z(n)=n^z$

显然，$id^z(n)$ 是一个完全积性函数，且直接求复杂度为 $O(n\log z)$。

因为是完全积性函数，所以只需要求解 $id^z(p_i)$，这一部分复杂度为 $O(\pi(n)\cdot \log z)=O(n)$。

线性筛法的复杂度为 $O(n)$，因此总复杂度也为 $O(n)$。

~~(这就是传说中的魔法吗！！)~~

一个简单的应用：求解 $\mu(n)$

鉴于 $\mu(n)$ 的特殊性，也只需要求出 $\mu(p_i)$。

写出的代码大致是这样的

int pri[N],notpri[N],pc,mu[N];
void Sieve_Mobius(int n){
    mu[1]=1;
    for(int i=2;i<=n;++i) {
        if(!notpri[i]) pri[++pc]=i,mu[i]=1;
        for(int j=1;j<=pc && 1ll*i*pri[j]<=n;++j) {
            notpri[i*pri[j]]=1;
            if(i%pri[j]==0) {
                mu[i*pri[j]]=0;
                break;
            }
            mu[i*pri[j]]=-mu[i];
        }
    }
}

真-应用: 大型模板

int CalcG(int n);

int prime[N],primecnt,notprime[N];
int F[N],D[N];
// F存储函数值
// D存储质因数出现的幂次积

void Sieve_Multiplicative_Function(int n){
    F[1]=1;
    for(int i=2;i<=n;++i){
        if(!notprime[i]) {
            prime[++primecnt]=i;
            for(ll j=i;j<=n;j*=i) F[j]=CalcG(j),D[j]=j;
            // 计算F(p_i^t)
        }
        for(int j=1;j<=primecnt && 1ll*i*prime[j]<=n;++j) {
            notprime[i*prime[j]]=1;
            int k=i*prime[j];
            if(i%prime[j]==0) {
                D[k]=D[i] * prime[j];
                F[k]=F[i/D[i]] * F[D[k]];
                break;
            }
            D[k]=prime[j];
            F[k]=F[i] * F[prime[j]];
        }
    }
}

杜教筛

用于求解 较大范围 且 可以构造出一些性质的积性函数前缀和

不推荐看我的，但是还是放一下链接

Min25筛

用于求 较大范围 且 使用范围更广 的积性函数前缀和，但在效率上不敌杜教筛

还是放一下链接

数论知识小结 [微提高篇]

数论知识小结 [微提高篇]

二次剩余和高次剩余

\(\mathrm{Miller\_Rabin}\) 素数检测

\(\mathrm{Miller\_Rabin}\)算法的步骤

可以结合 \(\mathrm{Miller Rabin}\) 的 \(n^{\frac{1}{3}}\) 特殊情况质因数分解

\(\text{Pollard's\_Rho}\)质因数分解

莫比乌斯函数

狄利克雷卷积

莫比乌斯反演

积性函数

线性筛筛法求解积性函数

一个最简单的应用: 在 \(O(n)\) 时间求解 \(id^z(n)=n^z\)

一个简单的应用：求解 \(\mu(n)\)

真-应用: 大型模板

杜教筛

Min25筛