数论筛小结

简单的整理了一下目前自己会的鬼畜东西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

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

杜教筛

显然对于积性函数 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筛

占坑

快速沃尔什变换

新的卷积

卷积的东西都很好玩呀。有时间一定好好学泛函.jpg

前面提到了,离散傅里叶变换的多项式卷积是对于每个 k 获得 i+j=k\sum a_i \times a_j,而在数论中比较多的狄利克雷卷积是对于每个 k 获得 i \times j = k\sum a_i \times a_j。在实际题目中,我们可能会遇到这样的一类卷积:

对于每个 k,获得 i \otimes j = k\sum a_i \times a_j。其中 \otimes 是任意按位逻辑运算,如 \&, |, \oplus 等。

很显然,我们如果按照最朴素的枚举方法:先枚举 i,再获得可行的 k,复杂度是 O(n^2) 朝上走的。如果 n \ge 10^5 不就完蛋了吗。按照这个架势,我们应该是要找复杂度为 O(n\log n)O(n \log \log n)O(n \log^2 n) 的算法。

很幸运的是,我们可以通过分治来完成这样的一件事情。当然了,由于位运算的值域是 2^n 级别的,我们也要像 FFT 那样将数列长度补齐。

快速沃尔什变换

注意到,位运算是有位独立性的。每一位之间并不会互相影响。那么,我们每次只考虑某一位?

我们令 A_{xy} = (A_{0y}, A_{1y})B_{xy} = (B_{0y}, B_{1y}),行向量分块,其中 y 是任意01序列,那么我们想要
C_{xy} = A_{xy} * B_{xy} = \left(\sum_{a \otimes b = 0} A_{ay} * B_{by}\ , \sum_{a \otimes b = 1} A_{ay} * B_{by} \right)
由于逻辑运算是确定的,我们可以很容易的计算出 \otimes 的真值表,并且后续又变成了规模更小的卷积,就是一个分治的过程啦。

假如构造了一个变换 \mathfrak{T}(A),满足 \mathfrak{T} (C) = \mathfrak{T} (A) \times \mathfrak{T} (B),并且可以很短时间内求得 \mathfrak{T}(A)\mathfrak{T}^{-1}(A),就可以像FFT一样卷积了。

Fast Walsh-Hadamard Transform,这个神奇的变换,我们分别称变换与逆变换为 FWT(A)UFWT(A),那么

对于与运算 \& 来说,有

FWT(A) = \left(\ FWT(A_0) + FWT(A_1)\ ,\ FWT(A_1)\ \right)
UFWT(A) = \left(\ UFWT(A_0) – UFWT(A_1)\ ,\ UFWT(A_1)\ \right)

并且

FWT(A)[i] = \sum_{i \& j = i} A[j]

void FWT(lld X[], int l, int r, int dft = 1)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);
    for (int i = 0; i <= m-l; i++)
        X[l+i] += X[m+1+i] * dft;
}

对于或运算 | 来说,有

FWT(A) = \left(\ FWT(A_0)\ ,\ FWT(A_0) + FWT(A_1)\ \right)
UFWT(A) = \left(\ UFWT(A_0)\ ,\ UFWT(A_1) – UFWT(A_0)\ \right)

并且

FWT(A)[i] = \sum_{i | j = i} A[j]

void FWT(lld X[], int l, int r, int dft = 1)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);
    for (int i = 0; i <= m-l; i++)
        X[m+1+i] += X[l+i] * dft;
}

异或运算 \oplus
FWT(A) = \left(\ FWT(A_0) + FWT(A_1)\ ,\ FWT(A_0) – FWT(A_1)\ \right)
UFWT(A) = \left(\ UFWT(\frac{A_0 + A_1}2)\ ,\ UFWT(\frac{A_0-A_1}{2})\ \right)

暂时没有找到比较明显的规律

void FWT(lld X[], int l, int r, int dft)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);

    for (int i = 0; i <= m-l; i++)
    {
        lld x = X[l+i], y = X[m+1+i];
        X[l+i] = dft == 1 ? x+y : (x+y)/2;
        X[m+1+i] = dft == 1 ? x-y : (x-y)/2;
    }
}

例子

链接:https://ac.nowcoder.com/acm/contest/295/H
来源:牛客网

Niuniu likes playing games. He has n piles of stones. The i-th pile has ai stones. He wants to play with his good friend, UinUin. Niuniu can choose some piles out of the n piles. They will play with the chosen piles of stones. UinUin takes the first move. They take turns removing at least one stone from one chosen pile. The player who removes the last stone from the chosen piles wins the game. Niuniu wants to choose the maximum number of piles so that he can make sure he wins the game. Can you help Niuniu choose the piles? 

给出 n 个数字,记为 a_0, a_1, a_2, …, a_{n-1},且 a_i \le 5\times10^5,求 max|A|, \oplus_{a\in A} a = 0

不妨记 \oplus_{i=0}^{n-1}a_i = sum,那么我们构造一个最小的堆,使得其异或和为 sum 即可。

我们只要记录可以被构造出来的堆值,就可以在第一次这个堆被构造出来时停止。由于 x \oplus x = 0,所以我们直接用已经构造出来的集合和原始给出的集合进行逻辑运算卷积。因为不需要记录方案数,所以直接置1即可。

B_{k}^n = \left[\left(\sum_{i \oplus j = k} A_{i} B_{j}^{n-1}\right) > 0 \right],相当于记录了,有 B 的堆和 A 原来堆,异或后能构造的值的集合。显然这个数字不会超过 2^{19},所以做19次卷积即可。

#include <cstring>
#include <cstdio>
typedef long long lld;
const int MAX = 524287;
lld a[MAX+1], b[MAX+1] = {1};

void FWT(lld X[], int l, int r, int dft)
{
    if (l == r) return;
    int m = (l+r)>>1;
    FWT(X, l, m, dft);
    FWT(X, m+1, r, dft);

    for (int i = 0; i <= m-l; i++)
    {
        lld x = X[l+i], y = X[m+1+i];
        X[l+i] = dft == 1 ? x+y : (x+y)/2;
        X[m+1+i] = dft == 1 ? x-y : (x-y)/2;
    }
}

int main()
{
    int n, tmp, sum = 0; scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        a[tmp]++;
        sum ^= tmp;
    }

    FWT(a, 0, MAX, 1);
    int max_ans = 0;
    while (!b[sum])
    {
        if (max_ans++ == 19) break;
        FWT(b, 0, MAX, 1);
        for (int j = 0; j <= MAX; j++)
            b[j] = a[j] * b[j];
        FWT(b, 0, MAX, -1);
        for (int j = 0; j <= MAX; j++)
            b[j] = !!b[j];
    }

    printf("%d\n", n - max_ans);
    return 0;
}