🌑

小羊儿的心情天空

数论筛小结

Dec 23, 2018 由 小羊

简单的整理了一下目前自己会的鬼畜东西QAQ

埃拉托斯特尼筛 / 普通筛

这个可能是小学课本就讲过的素数筛法吧。

每一个数(非1)的倍数一定是合数,那么把这些数字打上标记就可以了。

T(n)=O(i=2nni)O(1nnxdx)=O(nlogn)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(nloglogn)O(n \log \log n)

那么为什么今天我要提它呢?因为。我们可以来大区间素数筛选啊!

考虑这样的一个问题:求出 [a,b][a,b] 内的所有素数,其中 a109,ba106a \le 10^9, b-a \le 10^6。显然不能用线性筛。

我们可以发现这样的一个性质:[a,b][a,b] 中的每个合数,最大质因子一定不会超过 b\sqrt{b}

那么,这个筛就可以拿去用啦~

欧拉筛 / 线性筛

考虑某个数出现平方项后不再筛选它,就有了欧拉筛法。

对于任意一个整数 nn,如果它有一些的质数幂次超过1,那么它会被最小的那个质数筛选到。

如果没有,那么它会被最大的质因子筛选到。

另外介绍一下积性函数的概念:

ff 是定义在 Z+Z^+ 上的函数,如果满足 gcd(n,m)=1gcd(n,m)=1 则有 f(n)f(m)=f(nm)f(n)f(m) = f(nm),那么称为它是积性函数。

常见的积性函数有:

  • 欧拉函数 φ(n)=i=1n[gcd(i,n)=1]\varphi(n) = \sum_{i=1}^n [gcd(i,n)=1]

  • 莫比乌斯函数 μ(n)=(1)k or 0\mu(n) = (-1)^k\ or\ 0

  • 元函数 e(n)=[n=1]e(n) = [n=1]

  • 恒等函数 1(n)=11(n) = 1

  • 单位函数 id(n)=nid(n) = n

  • 幂函数 idk(n)=nkid^k(n) = n^k

  • 除数函数 σk(n)=dndk\sigma_k(n) = \sum_{d|n} d^k

  • 约数个数函数 d(n)=dn1d(n) = \sum_{d|n}1

  • 约数和函数 σ(n)=dnd\sigma(n) = \sum_{d|n}d

我们在做素数筛选的时候,由于我们的分界条件很明显,以两个数是否互质为标准,于是我们可以顺便求出可乘函数的所有值。

欧拉筛法代码如下。并且,由于每个数只会被访问一次,所以我们认为它的时间复杂度是 O(n)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(n), g(n) 是积性函数,我们称

(fg)(n)=i×j=nf(i)g(j)(f*g)(n)=\sum_{i\times j=n}f(i)g(j)

是这两个函数的狄利克雷卷积。很容易证明,fgf * g 依然是个积性函数。

那么,设 G={f  f is multiplicative function}G=\lbrace f\ |\ f\ is\ multiplicative\ function\rbrace,$ *$ 是按上述规则构成的运算,那么 (G,)(G, *) 构成了一个阿贝尔群,我们称这个群为积性函数的狄利克雷卷积群,其单位元就是 e(n)=[n=1]e(n)=[n=1]

列举群中的几个常见运算吧。

μ1=e\mu * 1 = e

φ1=id\varphi * 1=id

idμ=φid * \mu = \varphi

11=d1*1=d

μd=1\mu * d = 1

id1=σid * 1 = \sigma

idk1=σkid^k * 1 = \sigma_k

没错。其实在这个群中,μ\mu11 互为逆元。

杜教筛

显然对于积性函数 f(n)f(n) 和较大的 n1012n \ge 10^{12},我们很难线性计算 S(n)=i=1nf(n)S(n) = \sum_{i=1}^n f(n)

我们希望能找到一个 g(n)g(n),使得它们的狄利克雷卷积的求和尽可能方便地计算。

k=1nij=kg(i)f(j)=i=1nj=1n/ig(i)f(j)=i=1ng(i)S(ni)\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)=i=1n(fg)(i)i=2ng(i)S(ni)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)g(n)(fg)(n)(f*g)(n) 求和是线性的,那么计算的时间复杂度为

T(n)=O(i=1ni)+O(i=1nni)O(0nnxdx)=O(n34)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)S(n) 的前 n23n^\frac23 项,那么

T(n)=O(i=1n/kni)=O(nk)=O(n23)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(n23)O(n^\frac23) 计算了。

例如对于莫比乌斯函数的前缀和与欧拉函数的前缀和,我们有

M(n)=d=1nμ(d)=1d=2nM(nd)ϕ(n)=d=1nφ(d)=n(n+1)2d=2nϕ(nd)B(n)=d=1ndφ(d)=n(n+1)(2n+1)6d=2ndB(nd)\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筛

占坑