数论筛小结
Dec 23, 2018 由 小羊
简单的整理了一下目前自己会的鬼畜东西QAQ
埃拉托斯特尼筛 / 普通筛
这个可能是小学课本就讲过的素数筛法吧。
每一个数(非1)的倍数一定是合数,那么把这些数字打上标记就可以了。
T(n)=O(i=2∑n⌊in⌋)≈O(∫1nxndx)=O(nlogn)
最大的问题是,一个数如果之前被枚举到了,那么对它的倍数进行枚举是无用的操作。如果我们对已经打过标记的数不再枚举它的倍数,那么我们的复杂度约为 O(nloglogn)。
那么为什么今天我要提它呢?因为。我们可以来大区间素数筛选啊!
考虑这样的一个问题:求出 [a,b] 内的所有素数,其中 a≤109,b−a≤106。显然不能用线性筛。
我们可以发现这样的一个性质:[a,b] 中的每个合数,最大质因子一定不会超过 b。
那么,这个筛就可以拿去用啦~
欧拉筛 / 线性筛
考虑某个数出现平方项后不再筛选它,就有了欧拉筛法。
对于任意一个整数 n,如果它有一些的质数幂次超过1,那么它会被最小的那个质数筛选到。
如果没有,那么它会被最大的质因子筛选到。
另外介绍一下积性函数的概念:
设 f 是定义在 Z+ 上的函数,如果满足 gcd(n,m)=1 则有 f(n)f(m)=f(nm),那么称为它是积性函数。
常见的积性函数有:
-
欧拉函数 φ(n)=∑i=1n[gcd(i,n)=1]
-
莫比乌斯函数 μ(n)=(−1)k or 0
-
元函数 e(n)=[n=1]
-
恒等函数 1(n)=1
-
单位函数 id(n)=n
-
幂函数 idk(n)=nk
-
除数函数 σk(n)=∑d∣ndk
-
约数个数函数 d(n)=∑d∣n1
-
约数和函数 σ(n)=∑d∣nd
我们在做素数筛选的时候,由于我们的分界条件很明显,以两个数是否互质为标准,于是我们可以顺便求出可乘函数的所有值。
欧拉筛法代码如下。并且,由于每个数只会被访问一次,所以我们认为它的时间复杂度是 O(n) 的。
char miu[MAXN], c[MAXN], isnp[MAXN];
int phi[MAXN], d[MAXN], pri[MAXN], pcn;
void init_prime()
{
isnp[0] = isnp[1] = 1;
miu[1] = phi[1] = d[1] = 1;
for (int i = 2; i < MAXN; i++)
{
if (!isnp[i])
{
pri[pcn++] = i;
c[i] = 1;
d[i] = 2;
miu[i] = -1;
phi[i] = i-1;
}
for (int j = 0; j < pcn; j++)
{
int k = i * pri[j];
if (k >= MAXN) break;
isnp[k] = 1;
if (i % pri[j] == 0)
{
c[k] = c[i] + 1;
d[k] = d[i] / c[k] * (c[k]+1);
miu[k] = 0;
phi[k] = phi[i] * pri[j];
break;
}
else
{
c[k] = 1;
d[k] = 2 * d[i];
miu[k] = -miu[i];
phi[k] = phi[i] * (pri[j]-1);
}
}
}
}
狄利克雷卷积
设 f(n),g(n) 是积性函数,我们称
(f∗g)(n)=i×j=n∑f(i)g(j)
是这两个函数的狄利克雷卷积。很容易证明,f∗g 依然是个积性函数。
那么,设 G={f ∣ f is multiplicative function},$ *$ 是按上述规则构成的运算,那么 (G,∗) 构成了一个阿贝尔群,我们称这个群为积性函数的狄利克雷卷积群,其单位元就是 e(n)=[n=1]。
列举群中的几个常见运算吧。
μ∗1=e
φ∗1=id
id∗μ=φ
1∗1=d
μ∗d=1
id∗1=σ
idk∗1=σk
没错。其实在这个群中,μ 和 1 互为逆元。
杜教筛
显然对于积性函数 f(n) 和较大的 n≥1012,我们很难线性计算 S(n)=∑i=1nf(n)。
我们希望能找到一个 g(n),使得它们的狄利克雷卷积的求和尽可能方便地计算。
k=1∑nij=k∑g(i)f(j)=i=1∑nj=1∑⌊n/i⌋g(i)f(j)=i=1∑ng(i)S(⌊in⌋)
所以有
g(1)S(n)=i=1∑n(f∗g)(i)−i=2∑ng(i)S(⌊in⌋)
显然后面那个东西是可以进行分块计算的。
假设我们对 g(n) 和 (f∗g)(n) 求和是线性的,那么计算的时间复杂度为
T(n)=O⎝⎛i=1∑ni⎠⎞+O⎝⎛i=1∑n⌊in⌋⎠⎞≈O(∫0nxndx)=O(n43)
如果我们可以先用线性筛预处理出 S(n) 的前 n32 项,那么
T(n)=O⎝⎛i=1∑n/kin⎠⎞=O(kn)=O(n32)
我们就可以 O(n32) 计算了。
例如对于莫比乌斯函数的前缀和与欧拉函数的前缀和,我们有
M(n)=d=1∑nμ(d)=1−d=2∑nM(⌊dn⌋)ϕ(n)=d=1∑nφ(d)=2n(n+1)−d=2∑nϕ(⌊dn⌋)B(n)=d=1∑ndφ(d)=6n(n+1)(2n+1)−d=2∑ndB(⌊dn⌋)
洲阁筛
占坑
min_25筛
占坑