数论知识小结 [微提高篇]
(lastest updated on 2020.08.12)
二次剩余和高次剩余
(y^cequiv xpmod P)则(y)为(x)模(P)的(c)次剩余
关于二次剩余
( ext{Miller_Rabin})素数检测
(x)是质数的必要条件是
(forall a,a^{x-1}equiv 1pmod x)
同于对于一个质数(x)，必然有
(a^2equiv 1pmod x)的解只有(1,x-1)
证明是
(ecause a^2equiv 1 pmod x)
( herefore (a-1)(a+1)equiv 0 pmod x)
因为(x)是质数，所以(a-1mod x=0) 或 (a+1mod x=0)，即(ain{1,x-1})
( ext{Miller_Rabin})算法的步骤
将(x-1)分解为(x-1=2^scdot t)
找一个(<x)的质数(a)，求出(bequiv a^t pmod x)
将(b)进行(s)次平方，设这一次平方的结果(b^2equiv c pmod x)
当出现(c=1)时，(b)只能为(1),(x-1)否则(x)就不是质数
(s)次平方后，(bequiv a^{x-1}pmod x)，若(b e 1)，则(x)不是质数
不知道为什么，模板题跑5次就能过了。。。
注意(xleq 2or 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;
}
可以结合( ext{Miller_Rabin})的(n^{frac{1}{3}})特殊情况质因数分解
实际上，这种方法常用于求(n)的因子个数
方法非常简单，先对于所有(pri_ile n^{frac{1}{3}})的因子对于(n)筛去，剩下的部分中，所有质因子(>n^{frac{1}{3}})
因此最多包含两个质因数(可能相同)
用( ext{Miller_Rabin})判断是否只包含一个质数，然后简单判别两个质因数是否相同即可
复杂度为(O(log n+pi (n^{frac{1}{3}})))
小范围内比下面的( ext{Pollard's_Rho})更快，更简单
( ext{Pollard's_Rho})质因数分解
核心就是名字里的Rho(( ho))，是伪循环的一个形象的表示
伪循环：从某一个时刻开始，进入一个真循环，之前的时间就是( ho)的脚
构造伪随机函数(G_n(x)=(x^2+c)mod n)
构造数列(a_i=G_n(a_{i-1}))
由于函数的值域只有([0,n-1])，必然出现伪循环，即在从个位置开始，进入一个未知长度的循环，也就是长成了一个( ho)的形状
由于这个函数是伪随机函数，所以这个循环大小在期望情况下是(O(sqrt n))的
( ext{Pollard's_Rho})算法要找到一个(pin[2,n-2],p|n)
考虑用( ext{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 otin prime,exist pin[1,sqrt n],p|n)
所以期望情况下每(sqrt pleq sqrt {sqrt n}=n^{frac{1}{4}})的长度会出现循环
算法复杂度是期望(O(n^{frac{1}{4}}log n))的
那么写出( ext{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{egin{aligned}1 && n=1\ (-1)^m && exists c_i>1 \ 0 && exists c_i>1end{aligned} ight.)
狄利克雷卷积
对于数列(F,G)，他们的狄利克雷卷积(下简称(Foplus G))为
莫比乌斯反演
设元函数(E_i=1)
(G=Foplus E)，即(G_i=sum_{d|i}F_d)
由(G)反解(F)得到莫比乌斯反演(F_i=sum_{d|i}mu(d) G_{frac{i}{d}})
积性函数
积性函数的定义，对于一个定义在()上的函数(F(n))，若满足
(F(1)=1,forall (u,v)=1,F(u)cdot F(v)=F(ucdot v))，则(F(u))是一个积性函数
完全积性函数对于任意的(u,v)对满足上述性质
常见的积性函数有
1.元函数(e(n)=[n=1])
2.因数个数函数(d(n))
3.欧拉函数(varphi(n))
4.莫比乌斯系数(mu(n))
5.约数和函数(sigma(n))
推论：任意两个积性函数的狄利克雷函数卷积 仍然是积性函数
线性筛筛法求解积性函数
把积性函数(F(n))表示为
(F(n)=left{egin{aligned} 1 && n=1 \ G(n) && n=p_i^t \ prod G(p_i^{c_i}) && n=prod p_i^{c_i}end{aligned} ight.)
如果能在较短的时间内求得(G(p_i^t))，则可以用线性筛法求解积性函数(F(n))的前(n)项
一个最简单的应用: 在(O(n))时间求解(id^z(n)=n^z)
显然，(id^z(n))是一个完全积性函数，且直接求复杂度为(O(nlog 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筛
用于求 较大范围 且 使用范围更广 的积性函数前缀和 ， 但在效率上不敌杜教筛