与素数玩耍
例题: loj6235 区间素数个数
设 sum(x)表示小于等于 x 的素数个数。
假设我很蠢 (这件事根本不用假设好吗),连 10 以内的素数有哪些都不知道,只知道 1 不是素数。那么我就会令 sum(x)=x−1
然后我就会做一些事情来扔掉合数,于是我从小到大处理素数。假设我在处理素数 p,并且想要扔掉 sum(i)中以 p 为最小素因子的合数,我就会看向 sum(⌊ip⌋),由于前期扔掉了一些数,这个里面应该只有素数和素因子大于等于 p 的数,排除掉小于 p 的素数,剩下的数乘以 p 应该就是我们这一轮操作要扔掉的合数,也就是说,sum(i)−=sum(⌊ip⌋)−sum(p−1)
设 f1(x)=sum(x),f2(x)=sum(⌊nx⌋)。f1 和 f2 都只用开根号级别的空间。
那么我们就可以灵活运用 f1 和 f2 来完成筛法了。复杂度可以近似拟合为 O(n0.7)
你已经学会了与素数玩耍,可以来水一道题了:loj6202 叶氏筛法
其实和上一题差不多,只是公式变成了 sum(x)−=(sum(⌊ip⌋)−sum(p−1))×p
此外,如果你不想写高精的话,最后一个样例是过不去的……
与积性函数玩耍
例题:spoj-DIVCNTK
…… 看代码吧。关键思想是每个 f(x) 的贡献是在处理 x 的最大质因子时算上的,x 的最大质因子次数是 1 的时候可以用前缀和快速处理,否则可以枚举处理。
好吧,如果你看懂了上面那道题,那么再来一道?loj6053 简单的函数
这道题和上一道也差不多,就是我们要计算出质数异或 1 的前缀和。
于是我们可以筛出质数前缀和以及质数个数前缀和。由于质数中偶数只有 2,那么只有 2 异或 1 后会加 1,其他都会减 1,这样就能够把质数异或 1 的前缀和求出来了。
1 条评论
konnyakuxzy · 2018年3月15日 2:45 下午
Orz
千古神犇 FKL
扑通扑通跪下来
Orz
玩耍
太强啦 Orz