当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

大半年以前被集训队大爷 CMXRYNP 教育过一次,然而由于本人记忆力太差所以只能重新学习一遍。

前置技能

埃氏筛:本质上通过每个合数的最小的质因数来筛掉它,筛掉小于 n 的只需要做到小于 \sqrt n 的质数即可。

符号与约定

  • pmin_i 表示 i 最小的质因数
  • prime_i 表示第 i 个质因数

注意到 1 的性质比较特殊,往往将 f(1) 单独计算。

第一部分

通过这一部分我们需要求出

\forall x \in [1, n], \sum_{i=2}^{\lfloor \frac n x \rfloor} [i \text{ is prime}] f(i)

对于 f(i),在定义域为全体质数时,需要可以拆成 f(i) = \sum_k c_k i^k 的形式,其中 c_k 是常数。故我们只需要考虑形如 f(i) = i^k 即可。

g(a, b) = \sum_{i=2}^{a} [i \text{ is prime or } pmin_i > prime_b] i^k

这是可以递推的。我们先求得一个全集,然后利用筛法把不合法的筛去。

g(a, b) = \begin{cases} g(a, b - 1) & (a < prime_b^2) \\ g(a, b - 1) - prime_b^k \left(g(\lfloor \frac a {prime_b} \rfloor, b - 1) - g(prime_{b-1}, b - 1) \right) & (a \geq prime_b^2) \\ \end{cases}

每次把最小质因数是 prime_b 的给删掉。

  • 如果 a < prime_b,显然没什么可以删的了
  • 如果 a \geq prime_b,由于 f(i) 是积性函数,被删的数一定都会产生一个 prime_b^k 的贡献,然后我们将这个数除以 prime_b 就可以利用之前的计算结果了
    • g(\lfloor \frac a {prime_b} \rfloor, b - 1) 表示被删的数,如果一个数有比 prime_b 更小的质因子则再这里已经被筛掉了,故不会算重
    • g(prime_{b-1}, b - 1) 注意到我们把 i 是质数的情况多减了,需要加回去

a 每次只会不断除以一个数并下取整,注意到 \lfloor \frac a {bc} \rfloor = \lfloor \frac {\lfloor \frac a b \rfloor} c \rfloor,故所有的 a 都可以被表示为 \lfloor \frac n x \rfloor 的形式,并且这样的数只有 O(\sqrt n) 个。

第二部分

S(a, b) = \sum_{i=2}^a [a \text{ is prime or } pmin_i \geq prime_b] f(i)

我们需要求得 S(n, 1),这是比较困难的。由于照样可以递推,这次我们先求得一个子集,然后通过筛法求得全集。

S(a,b)= \begin{cases} S(a,b+1) & a<prime_b^2 \\ S(a,b+1) + \sum\limits_{prime_b^{i+1} \le a} \left(f(prime_b^i) \left(S(\lfloor \frac{a}{prime_b^i} \rfloor, b+1) - g(prime_b, \infty)\right) + f(prime_b^{i+1}) \right) & a\ge prime_b^2 \end{cases}

与上面类似,我们加上由满足 pmin_x = prime_bx 带来的贡献,再减掉质数导致多算的这一部分即可。

不细讲了,注意需要枚举指数。

Min_25 筛

已有 8 条评论

  1. Gu gu gu Gu gu gu

    有没有代码啊(

    1. 之前写过,懒得放了,可以看 CMXRYNP 的博客里的代码,比我的实现简洁很多。

  2. Orz memset0

  3. Orz memset0

  4. orz memset0

  5. orz wyl orz wyl

    orz wyl
    ddzz /kel

配置 SSH config 使用跳板机连接
上一篇 «
LOJ6035 「雅礼集训 2017 Day4」洗衣服
» 下一篇