其实求\(x\)以内素数个数,有时间复杂度为\(O(x^{2/3}loglogx)\) ,空间复杂度为\(O(x^{1/3})\)优秀算法

\(prime(i)\)表示第\(i\)个素数。

\(\pi(x)\)表示小于等于\(x\)的素数个数。

\(\phi(x, a)\)表示小于等于\(x\)的数中,不被前\(a\)个素数整除的数的个数,特别地,\(\phi(x, 0) = x\)

\(\phi(x, a)\)分类,其中\(P_k(x, a)\)表示小于等于\(x\)的数中,不被前\(a\)个素数整除且有且仅有\(k\)个素数因子的数的个数,特别地,\(P_0(x, a) = 1\)。那么有,\(\phi(x,a) = P_0(x, a) + P_1(x, a) + \dots + P_k(x, a) + \dots\)

考虑到,

\[\pi(x) = P_1(x, a) + a = \phi(x, a) - P_0(x, a) - \sum_{k = 2}^{\infty}P_k(x, a) + a = \phi(x, a) -1 - \sum_{k = 2}^{\infty}P_k(x, a) + a\]

所以,对于特定的\(a\),我们只需要知道\(\phi(x, a)\)\(\sum_{k = 2}^{\infty}P_k(x, a)\),就可以计算出\(\pi(x)\)

\(a = \pi(x ^ {1 / 3})\),那么\(P_3(x, a) = P_4(x, a) = \dots = 0\),也就是说我们只需要计算\(\phi(x, a)\)\(P_2(x, a)\)

先考虑如何计算\(\phi(x, a)\)

注意到\(\phi(x, a - 1)\)\(\phi(x, a)\)多了那些不被前\(a - 1\)个素数整除但可以被\(prime(a)\)整除的数,即多了\(\phi(\frac{x}{prime(a)}, a - 1)\)。因此,\(\phi(x, a) = \phi(x, a - 1) - \phi(\frac{x}{prime(a)}, a - 1)\)

我们解这个递归式就可以计算出\(\phi(x, a)\)

假设我们能够解这个递归式,那么我们如何计算时间复杂度呢?

因为这个递归树是一棵满二叉树,所以叶子结点个数\(n_0\)与非叶结点个数\(n_2\)满足\(n_0 = n_2 + 1\),也就是说时间复杂度为\(O(n_0 + n_2) = O(2n_0 - 1) = O(n_0)\),因此我们只需要考虑递归树的叶子结点就好了。

因为递归树上的任一结点都可以被唯一地表示为\(\phi(\frac{x}{n}, b)\),那么有一个显然的递归边界如下:

  1. \(b = 0\)\(\phi(\frac{x}{n}, b) = \frac{x}{n}\)
  2. \(\frac{x}{n} \leq prime(b)\)\(\phi(\frac{x}{n}, b) = 1\)

不过可以证明,这样的递归边界会使时间复杂度至少为\(\Omega(\frac{x}{log^3x})\)。考虑\(n\)\(3\)个小于等于\(x^{1/3}\)的素数的乘积,由于\(prime(b) \leq x^{1/3}\),因此必定存在叶子结点\(\phi(\frac{x}{n}, b)\)。根据素数定理,小于等于\(x^{1/3}\)的素数大概有\(\frac{x^{1/3}}{logx^{1/3}}\)个,故递归树至少有\(\Omega(\frac{x}{log^3x})\)个叶子结点,达不到之前所说\(O(x^{2/3}loglogx)\)这样的时间复杂度。

现在考虑修改递归边界如下:

  1. \(b = 0\)并且\(n \leq x^{1/3}\)
  2. \(n > x^{1/3}\)

Read More

\(B_n\)表示将\(n\)个不同的元素划分为若干非空集合的方案数。

递推式:\(B_{n + 1} = \sum_{k = 0}^nC(n, k)B_k\)

证明:考虑第\(n+1\)个元素,可以把它和\(k\)个其他元素划分在一起,那么剩余\(n - k\)个元素有\(B_{n - k}\)种划分。

递推式:\(B_n = \sum_{k = 0}^nStirling2(n, k)\)

证明:\(Stirling2(n, k)\)表示将\(n\)个不同的元素划分为\(k\)个非空集合的方案数。

Bell三角

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

  1. \(b(0, 0) = 1\)
  2. \(b(i, 0) = b(i - 1, i - 1)\)
  3. \(b(i, j) = b(i, j - 1) + b(i - 1, j - 1)\)

Read More

B

采用数学归纳法证明Fi(m)为Ti的边集:

  1. 当i = 1时。当前没有被使用的边的集合为L1(m),因为图连通,所以通过Kruskal算法插入L1(m)后,所得到的生成森林一定是一棵最小生成树,即T1。又因为F1(m)为通过Kruskal算法插入L1(m)后得到的生成森林的边集,所以F1(m)为T1的边集,命题成立。
  2. 假设i = k时,成立。则当i = k + 1时,当前没有被使用的边的集合为L1(m) \ F1(m) \ F2(m) \ ... \ Fk(m) = L2(m) \ F2(m) \ ... \ Fk(m) = Lk(m) \ Fk(m) = Lk+1(m)。因为图连通,所以通过Kruskal算法插入Lk+1(m)后,所得到的生成森林一定是一棵最小生成树,即Tk+1。又因为Fk+1(m)为通过Kruskal算法插入Lk+1(m)后所得到的生成森林的边集,所以Fk+1(m)为Tk+1的边集,命题成立。

综上所述,对于正整数i,Fi(m)为Ti的边集。

C

这个就不采用过于形式化的证明了。

题目想说的是,如果两个点(u, v)在(V, Fi(t))中属于同一连通分量,那么对于任意的j < i,(u, v)在(V, Fj(t))中也属于同一连通分量。

这个是由Kruskal算法造成的,Kruskal算法每次选一条边,判断这两个点是否在同一个连通分量中,如果在,则放弃这条边,如果不在,则将选择这条边,并将两个点合并到同一连通分量中。

(u, v)在(V, Fi(t))中属于同一连通分量,那么这条连接(u, v)的边一定是在(V, Fj(t))中被放弃过的,所以(u, v)在(V, Fj(t))中属于同一连通分量。

Read More

题意

Alice想要得到一个长度为\(n\)的序列,序列中的数都是不超过\(m\)的正整数,而且这\(n\)个数的和是\(p\)的倍数。Alice还希望,这\(n\)个数中,至少有一个数是质数。Alice想知道,有多少个序列满足她的要求,答案对\(20170408\)取模。

其中,\(1 \leq n \leq 10^9\)\(1 \leq m \leq 2 \times 10^7\)\(1 \leq p \leq 100\)

Read More

题意

\(m\)个石头围成一个圆圈,编号从\(0\)\(m - 1\)\(n\)只青蛙,编号从\(1\)\(n\)。第\(i\)只青蛙只能跳\(a_i\)步,即从\(j\ mod\ m\)\((j + a_i)\ mod\ m\)。求被青蛙踩过的石头的编号和,每个石头的编号只算一次。

不超过\(20\)组数据,其中,\(1 \leq m \leq 10^9\)\(1 \leq n \leq 10^4\)

Read More