Mathematics(3):莫比乌斯反演与杜教筛 2019-05-10

Something useful

  • \(\lfloor \frac{n}{i}\rfloor\)只有\(O(\sqrt n)\)种取值
  • 对于\(i\)\(\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor\)是与\(i\)\(n\)除并下取整取值相同的一段区间的右端点
  • \(\left\lfloor\frac{n}{ab}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{n}{b}\right\rfloor}{a}\right\rfloor\)
  • Möbius function

    \(\mu\)表示莫比乌斯函数。 \[n=p_1^{q_1}p_2^{q_2}...p_k^{qk}\\\mu(n)=\begin{cases} 1 & (x=1) &\\ 0 & (\max_{i}^{n} p_i>1) \\ (-1)^{k} & \text{otherwise}\end{cases}\]

    一个有用的性质 \[\sum_{d|n}\mu(d)=[n=1]\] 证明:考虑\(d|n\)相当于在\(n\)的因子中选择若干个,然后把这些因子组成的数的\(\mu\)加起来,如果有一个数的次数大于\(1\)\(\mu = 0\)对答案没有贡献,所以这个\(\mu\)值只与选择的质因子的个数的奇偶性有关,也就是说只考虑每个质因子是否选择。 \[\text{if}~~~n =1~~~\mu(1)=1\\\text{else}~~~n=p_1^{q_1}p_2^{q_2}...p_k^{qk}\\\sum_{d|n}\mu(d)=\binom{k}{0}-\binom{k}{1}+\binom{k}{2}-\binom{k}{3}...+(-1)^k\binom{k}{k}\\\sum_{d|n}\mu(d)=\sum_{i=0}^{k}(-1)^i\binom{k}{i}\\\because (1+x)^{k}=\sum_{i=0}^{k}\binom{k}{i}x^i\\\therefore x=-1\\\sum_{d|n}\mu(d)=\sum_{i=0}^{k}(-1)^i\binom{k}{i}=(1+(-1))^k = 0\\\]

    IL void Sieve() {
        mu[1] = 1;
        for (int i = 2; i < maxn; ++i) {
            if (!flag[i]) {
                prime[++prime[0]] = i;
                mu[i] = -1;
            }
            for (int j = 1; j <= prime[0] && i * prime[j] < maxn; ++j) {
                int v = i * prime[j]; flag[v] = 1;
                if (i % prime[j] == 0) break;
                else mu[v] = -mu[i];
            }
        }
    }
    

    Dirichlet product

    \(f,g\)为数论函数,定义 \[h=f*g \rightarrow h(n)=\sum_{d|n, d > 0}f(d)\times g(\frac{n}{d})\\\] 狄利克雷卷积满足交换律结合律分配率

    常见的积性函数:

  • \(\mu\),莫比乌斯函数。
  • \(\varphi\) ,欧拉函数。
  • \(d\) ,约数个数。\(d(n)\)表示 \(n\) 的约数的个数。
  • \(\sigma\) ,约数和函数。\(\sigma(n)\)表示 \(n\) 的各个约数之和。
  • 常见的完全积性函数:

  • \(\epsilon\) ,元函数。 \(\epsilon(x)=[x=1]\)
  • \(I\) ,恒等函数。 \(I(n)=1\)
  • \(id\) ,单位函数。\(id(n)=n\)
  • 常用的狄利克雷卷积 : \[\begin{cases}I * \mu = \epsilon\\\mu * id = \varphi\\I * id = \sigma\\I * I = d\\I * \varphi = id\end{cases}\]

    Möbius inversion formula

    对于数论函数\(f, g\) \[\begin{aligned}f(n)&=\sum_{d|n}g(d)\\f &= g * I\\f * \mu &= g * I * \mu\\f * \mu &= g * (I * \mu)\\f * \mu &=g * \epsilon\\f * \mu &= g\\\end{aligned}\] 然后得到了 \[g(n)=\sum_{d|n}f(d)\times \mu(\frac{n}{d})\] 对于另一个式子 \[\begin{aligned}f(n)&=\sum_{n|d}^{d\leq L}g(d)\\g(n)&=\sum_{n|d}^{d\leq L}f(d)\times \mu(\frac{d}{n})\end{aligned}\]

    Tricks

  • \(\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=d]\)

    \(f(d)\)表示集合中\((i,j)=d\)的倍数的数的\((i,j)\)的个数,\(g(d)\)表示\((i,j)=d\)的数的个数(我们要求的答案是\(g(d)\))。 \[\begin{aligned}f(d)&=\lfloor{\frac{n}{d}}\rfloor\lfloor\frac{m}{d}\rfloor\\&=\sum_{d|t}^{\min(n,m)}g(t)\\g(d)&=\sum_{d|t}^{\min(n,m)}f(t) \mu(\frac{t}{d})\\&=\sum_{d|t}^{\min(n,m)}\lfloor{\frac{n}{t}}\rfloor\lfloor\frac{m}{t}\rfloor\mu(\frac{t}{d})\end{aligned}\] 小技巧:

    \(\sigma(n)\)\(n\)的约数个数,因为\(I * id = \sigma\)

  • \[\sigma(nm)=\sum_{i|n}^{n}\sum_{j|m}^{m}[(i,j)=1]\]

  • \(\sum_{i}^{n}\sum_{j=1}^{m}[(i,j)\in \text{Prime}]\) \[\sum_{p\in Prime}\sum_{p|t}^{\min(n,m)}\lfloor{\frac{n}{t}}\rfloor\lfloor\frac{m}{t}\rfloor\mu(\frac{t}{p})\] 对于所有\(t=p(Prime) \times \frac{t}{p}\),预处理\(\text{pre[t]}\)\[\begin{aligned}\text{pre[t]}&=\sum_{p|t}\mu(\frac{t}{p})\\ans&=\sum_{t}^{\min(n,m)}\text{pre[t]}\lfloor{\frac{n}{t}}\rfloor\lfloor\frac{m}{t}\rfloor\end{aligned}\]

    预处理\(\text{pre}\)可以枚举质数然后用调和级数,同时也可以在线筛的时候算。

    考虑\(\text{prime[j]} \not| i\),加入\(\text{prime[j]}\)会让\(\mu\to -u\),之前的\(f[i]\)变为\(-f[i]\),贡献为\(\mu[i]\)\(f[i \times prime[j]]=-f[i]+mu[i]\)

    如果\(\text{prime[j]}| i\),加入\(\text{prime[j]}\)让除了\(i\)的所有因子上有一个\(prime[j]^2\),此时\(f[i\times prime[j]]=mu[i]\)

  • \(\sum_{i=1}^{n}\sum_{j=1}^{m}(i,j)^k\) \[\sum_{p}\sum_{p|t}^{\min(n,m)}\lfloor{\frac{n}{t}}\rfloor\lfloor\frac{m}{t}\rfloor\mu(\frac{t}{p})p^k\\\sum_{p}p^k\sum_{p|t}^{\min(n,m)}\mu(\frac{t}{p})\lfloor{\frac{n}{t}}\rfloor\lfloor\frac{m}{t}\rfloor\] 同上,我们可以预处理\(\text{pre[t]}\) \[\text{pre[t]}=\sum_{d|t}d^k\mu(\frac{t}{d})\] 由于\(\mu\)是积性函数,\(d^k\)也是积性函数,所以\(pre[t]\)是积性函数

    对于\(\text{pre}[p^x], p \in \text{Prime}\),由于\(\mu(p^2)\)以上都是0,对答案无贡献。 \[\begin{aligned}pre(p^x)&=(p^{x}\cdot\mu(1) + p^{k(x-1)}\cdot \mu(p)) & p \in \text{Prime}\\\end{aligned}\] 一般地 \[\begin{aligned}pre(n)&= \sum_{d \mid n}d^k\mu(\frac T d)\\&= \prod_{p_i} pre(p_i^{x_i})\\&= \prod_{p_i} (p_i^{x_i}\cdot\mu(1) + p_i^{k(x_i-1)}\cdot \mu(p_i))\\&= \prod_{p_i} p_i^{k(x_i-1)}(p_i^k-1)\end{aligned}\]

  • Du's Sieve

  • \(\mu\)前缀和
  • \[\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{d|i}\mu(d)&=1\\\sum\limits_{i=1}^n\sum\limits_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\mu(j)&=1\\\sum_{i=1}^{n}\mu(i)&=1-\sum_{i=2}^{n}\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\mu(j)\end{aligned}\] 考虑右边式子,由于是\({\left\lfloor\frac{n}{i}\right\rfloor}\),所以只有\(\sqrt n\)种不同的取值,\(\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\mu(j)\)是一个前缀和的性质,于是可以递归求,求的过程中用hash表实现记忆化防止复杂度退化。

    时间复杂度(这里本来有式子但是学完积分发现它错了,直接给出结论)
    \[\begin{aligned} O(n^{\frac{3}{4}}) \end{aligned}\] 注意到\(n\)比较小的时候可以线性筛出来。 \[O\left(B+\sum\limits_{i=1}^{\frac nB}\sqrt{\frac ni}\right)=O\left(B+\frac n{\sqrt{B}}\right)\] 根据均值不等式当\(B=n^{\frac{2}{3}}\)有最低复杂度\(O(n^{\frac{2}{3}})\)

  • \(\varphi\)前缀和 \[\begin{aligned}\because \sum_{d|n}\varphi(d)&=n\\\therefore \sum_{i=1}^{n}\sum_{d|i}\varphi(d)&=\sum_{i=1}^{n}\\&=\frac{n(n+1)}{2}\\\sum_{i=1}^{n}\varphi(i)&=\frac{n(n-1)}{2}-\sum_{i=2}^{n}\sum_{j=1}^{\left\lfloor\frac{n}{i}\right\rfloor}\varphi(j)\end{aligned}\] 做法和复杂度同上。