简单的整理了一下目前自己会的鬼畜东西QAQ
埃拉托斯特尼筛 / 普通筛
这个可能是小学课本就讲过的素数筛法吧。
每一个数（非1）的倍数一定是合数，那么把这些数字打上标记就可以了。
T(n) = O\left(\sum_{i=2}^{n}\left\lfloor\frac{n}{i}\right\rfloor\right) \approx O\left(\int_1^n\frac{n}{x}dx\right) = O(n \log n)
最大的问题是，一个数如果之前被枚举到了，那么对它的倍数进行枚举是无用的操作。如果我们对已经打过标记的数不再枚举它的倍数，那么我们的复杂度约为 O(n \log \log n)。
那么为什么今天我要提它呢？因为。我们可以来大区间素数筛选啊！
考虑这样的一个问题：求出 [a,b] 内的所有素数，其中 a \le 10^9, b-a \le 10^6。显然不能用线性筛。
我们可以发现这样的一个性质：[a,b] 中的每个合数，最大质因子一定不会超过 \sqrt{b}。
那么，这个筛就可以拿去用啦~
欧拉筛 / 线性筛
考虑某个数出现平方项后不再筛选它，就有了欧拉筛法。
对于任意一个整数 n，如果它有一些的质数幂次超过1，那么它会被最小的那个质数筛选到。
如果没有，那么它会被最大的质因子筛选到。
另外介绍一下积性函数的概念：
设 f 是定义在 Z^+ 上的函数，如果满足 gcd(n,m)=1 则有 f(n)f(m) = f(nm)，那么称为它是积性函数。
常见的积性函数有：
- 欧拉函数 \varphi(n) = \sum_{i=1}^n [gcd(i,n)=1]
-
莫比乌斯函数 \mu(n) = (-1)^k\ or\ 0
-
元函数 e(n) = [n=1]
-
恒等函数 1(n) = 1
-
单位函数 id(n) = n
-
幂函数 id^k(n) = n^k
-
除数函数 \sigma_k(n) = \sum_{d|n} d^k
-
约数个数函数 d(n) = \sum_{d|n}1
-
约数和函数 \sigma(n) = \sum_{d|n}d
我们在做素数筛选的时候，由于我们的分界条件很明显，以两个数是否互质为标准，于是我们可以顺便求出可乘函数的所有值。
欧拉筛法代码如下。并且，由于每个数只会被访问一次，所以我们认为它的时间复杂度是 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)=\sum_{i\times j=n}f(i)g(j)
是这两个函数的狄利克雷卷积。很容易证明，f * g 依然是个积性函数。
那么，设 G=\lbrace f\ |\ f\ is\ multiplicative\ function\rbrace， * 是按上述规则构成的运算，那么 (G, *) 构成了一个阿贝尔群，我们称这个群为积性函数的狄利克雷卷积群，其单位元就是 e(n)=[n=1]。
列举群中的几个常见运算吧。
\mu * 1 = e
\varphi * 1=id
id * \mu = \varphi
1*1=d
\mu * d = 1
id * 1 = \sigma
id^k * 1 = \sigma_k
没错。其实在这个群中，\mu 和 1 互为逆元。
杜教筛
显然对于积性函数 f(n) 和较大的 n \ge 10^{12}，我们很难线性计算 S(n) = \sum_{i=1}^n f(n)。
我们希望能找到一个 g(n)，使得它们的狄利克雷卷积的求和尽可能方便地计算。
\sum_{k=1}^n \sum_{ij=k} g(i)f(j) = \sum_{i=1}^n\sum_{j=1}^{\lfloor n/i \rfloor}g(i)f(j) = \sum_{i=1}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
所以有
g(1)S(n) = \sum_{i=1}^n(f*g)(i) – \sum_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
显然后面那个东西是可以进行分块计算的。
假设我们对 g(n) 和 (f*g)(n) 求和是线性的，那么计算的时间复杂度为
T(n) = O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{i}\right) + O\left(\sum_{i=1}^{\sqrt{n}}\sqrt{\left\lfloor\frac{n}{i}\right\rfloor}\right) \approx O\left(\int_0^{\sqrt{n}}\sqrt{\frac{n}{x}}dx\right) = O\left(n^\frac{3}{4}\right)
如果我们可以先用线性筛预处理出 S(n) 的前 n^\frac23 项，那么
T(n) = O\left(\sum_{i=1}^{n/k}\sqrt{\frac{n}{i}}\right) = O\left(\frac{n}{\sqrt{k}}\right) = O\left(n^\frac{2}{3}\right)
我们就可以 O(n^\frac23) 计算了。
例如对于莫比乌斯函数的前缀和与欧拉函数的前缀和，我们有
\begin{aligned} & M(n) = \sum_{d=1}^n\mu(d) = 1-\sum_{d=2}^nM\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\\\ & \phi(n) = \sum_{d=1}^n\varphi(d) = \frac{n(n+1)}2-\sum_{d=2}^n\phi\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \\\\ & B(n) = \sum_{d=1}^nd\varphi(d) = \frac{n(n+1)(2n+1)}6-\sum_{d=2}^ndB\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{aligned}
洲阁筛
占坑
min_25筛
占坑