博客测试页

发表于 更新于 分类于 阅读次数：

这里是摘要。

[TOC]

一级标题

二级标题

三级标题

正文部分，嘿嘿。

代码块

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>

using namespace std;

int main()
{
    cout << "Hello, World!" << endl;
    return 0;
}

目标：求 \(g(n)=\sum_{p\le n} f(p)\) 。

不妨设 \(f(p)\) 是完全积性函数，如果不是可以尝试拆成若干项完全积性函数，分别求然后相加。

首先要线性筛求出 \(\sqrt n\) 以内的质数。

\(g(n)\) 很难直接求解，考虑用 DP 计算。设 \(g(n,j)=\sum_{i=1}^nf(i)[i\text{是质数或其最小质因子}>p_j]\)，其中 \(p_j\) 表示第 \(j\) 个质数，那么我们要的就是 \(g(n,k),k\text{为最小的满足}p_k\ge \sqrt n\)。考虑从 \(j-1\) 变到 \(j\) ，那么最小质因子为 \(p_j\) 的合数会被筛掉，那么它们的贡献要减去。则有转移 \[ g(n,j)=g(n,j-1)-f(p_j)\left(g\left(\left\lfloor\frac{n}{p_j}\right\rfloor,j-1\right)-g(p_{j-1},j-1)\right) \] 系数 \(f(p_j)\) 表示由于 \(f(p)\) 是完全积性函数，所以可以把它从后面提出来。 \(g\left(\left\lfloor\frac{n}{p_j}\right\rfloor,j-1\right)\) 表示考虑所有 \(p_j\) 的倍数，它们除以 \(p_j\) 之后，最小质因子 \(>p_{j-1}\) 的合数以及所有质数的贡献，应当减去。但是，这些质数中可能有 \(\le p_{k-1}\) 的，它们在之前就被筛掉过了，所以要加回来，也就是 \(g(p_{j-1},j-1)\)。

由于有公式 \(\lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor=\lfloor\frac{a}{bc}\rfloor\) ，因此容易发现上述式子只会用到形如 \(\lfloor\frac{n}{x}\rfloor,x\le n\) 的点处的 DP 值，即第一项的状态数是 \(O(\sqrt n)\)（实际实现的时候注意状态数是 \(2\sqrt n\)）。我们预处理出这 \(O(\sqrt n)\) 个数，把他们离散化，顺带求出 \(g(x,0)\)，然后 DP 即可。

注意到上述转移式中还有一项 \(g(p_{j-1},j-1)\)，我们只处理了所有形如 \(\lfloor\frac{n}{x}\rfloor\) 的数，是否会漏掉某些质数 \(p\) 呢？其实不会漏。注意到，能用来转移的 \(p\) 一定满足 \(p \le \sqrt n\)。我们只需要证明 \(\forall k \le \sqrt n, \exists x,k=\lfloor\frac{n}{x}\rfloor\)。

证明：

  1. 若 \(k=\lfloor\sqrt n\rfloor\)，设 \(n=k^2+d\)，则由于 \(k^2\le n < (k+1)^2\)，故 \(d\in[0,2k]\)。
    1. \(d\in [0,k)\)，那么 \(\lfloor\frac{n}{k}\rfloor=k+\lfloor\frac{d}{k}\rfloor=k\)。
    2. \(d\in [k,2k]\)，那么 \(\lfloor\frac{n}{k+1}\rfloor=\lfloor\frac{k^2+k+d-k}{k+1}\rfloor=k+\lfloor\frac{d-k}{k+1}\rfloor=k\)。
  2. 若 \(k < \lfloor\sqrt n\rfloor\) 即 \(k \le \sqrt n - 1\)，假设存在 \(i,\lfloor\frac{n}{i+1}\rfloor<k<\lfloor\frac{n}{i}\rfloor\)，此时 \(k\) 恰好夹在两个连续的 \(\lfloor\frac{n}{x}\rfloor\) 之间，即不可被表出。则 \(\frac{n}{i+1}<k\)，故 \(n<k(i+1)\)，从而 \(k<\lfloor\frac{n}{i}\rfloor<\lfloor\frac{k(i+1)}{i}\rfloor=k+\lfloor\frac{k}{i}\rfloor\)。另一方面，\(\frac{n}{i+1}<k<\sqrt n\)，所以 \(i+1>\sqrt n\)，于是 \(i>\sqrt n - 1 \ge k\)，因此 \(\lfloor\frac{k}{i}\rfloor=0\)，于是得到 \(k<k\)，故假设不成立，原命题成立。

所以，上述担心就是多虑了。

我看到很多博客、题解都额外预处理了 \(\sqrt n\) 内所有素数处的函数值的前缀和，但因为我“粗心”，代码中直接调用 \(g\) 数组，却顺利通过了一堆题目，写笔记时意识到这一点，于是琢磨出了奥妙所在。其实，在看 zzt 集训队论文时注意到他说只需要用到 \(\lfloor\frac{n}{x}\rfloor\) 处的值，就心生疑惑，现在终于明白了。因此，在我看来，预处理根号内素数处的函数前缀和的值是不必要的。

时间复杂度

\[ \begin{aligned}&\sum_{i\le \sqrt n}O(\pi(\sqrt i))+\sum_{i\le \sqrt n}O(\pi(\sqrt\frac{n}{i}))\\ =&\sum_{i\le \sqrt n}O(\pi(\sqrt\frac{n}{i}))\\ =&\sum_{i\le \sqrt n}O\left(\frac{\sqrt\frac{n}{i}}{\log\sqrt\frac{n}{i}}\right)\\ =&O\left(\int_1^{\sqrt n} \frac{\sqrt\frac{n}{x}}{\log\sqrt\frac{n}{x}}\right)\\ =&O\left(\frac{n^\frac{3}{4}}{\log n}\right) \end{aligned} \]