闲话
？本来想颓一整天的
不知不觉就到现在了呢
不是很理解
jijidawang 数个月前莫比乌斯反演就爆踩我了%%%%
最近闲话的阅读量忽高忽低欸
不懂不懂 溜了溜了
\(\text{Min_25}\) 筛
前置知识。
做法见《〈整点计数〉命题报告以及对高斯整数的若干研究》，徐翊轩，2019。
写得确实挺详细的，式子啥的都有了。
推荐阅读：社论 22.10.20 二维圆周数点与高斯整数环。
求满足 \(1< p \leq n\) 的质数 \(p\) 有多少个。
\(n \le 10^{11}\)。
应该算是 \(\text{Min_25}\) 筛的第一部分的板子了。
我们构造 \(f(n) = 1\)，通过第一部分的递推就能得到答案。
求满足 \(1< p \leq n\) 且 \(p\) 的二进制表示最后两位为 \(01\) 的质数 \(p\) 有多少个。
\(n \le 3\times 10^{10}\)。
直接做肯定不好做。
我们发现，这样的一个函数是完全积性的：
\[f(n) = \left\{ \begin{aligned} &1 ,\ & n\bmod 4 = 1, \\ &-1 ,\ & n\bmod 4 = 3, \\ &0 ,\ & \text{otherwise.} \\ \end{aligned} \right.\]证明显然。
因此可以借助 \(\text{Min_25}\) 筛的第一部分求得 \(f\) 在质数处的前缀和。
我们发现，答案是模 \(4\) 余 \(1\) 的质数数 - 模 \(4\) 余 \(3\) 的质数数。因此求得质数前缀和后两个答案相加除以 \(2\) 就能得到答案。
质数前缀和见例题 \(2\)。
设
\[f(n) = \prod_{d|n} \mu(d) \]求
\[\sum_{i=1}^n f(i) \pmod {998244353} \]\(n \le 10^{10}\)。
%%% Alpha1022
首先 \(f(n)\) 在质数处的取值是 \(-1\)。然后在有平方因子的数的取值是 \(0\)。那在其余地方呢？
假设 \(n\) 有 \(k > 1\) 个质因子。这导出了
因此我们有其余地方的值为 \(1\)。
首先考虑 \(|f(n)|\) 是什么。容易发现这个东西和 \(\mu^2\) 的表现相同。证明考虑构造贝尔级数。
然后只需要求出 \(\mu^2\) 的前缀和后减去两倍的质数个数就行了。
下面的推导来自 jijidawang。赞美 jijidawang！
\[ \begin{aligned} &\sum_{i=1}^n \mu^2(i) \\ = & \sum_{i=1}^n \sum_{d|i} \sum_{e|d} \mu(e)\mu^2\left(\frac de\right) \qquad &(\mu^2 = \mu^2 * \mu * \text I) \\ = & \sum_{i=1}^n \sum_{d|i} \sum_{e|q} \mu(pe)\mu^2\left(\frac {p^2q}{pe}\right) \qquad &(令\ d = p^2 q, \ (p, q) = 1) \\ = & \sum_{i=1}^n \sum_{d|i} \sum_{e|q} \mu(p)\mu(e)\mu^2\left(p\right)\mu^2\left(\frac {q}{e}\right) \\ = & \sum_{i=1}^n \sum_{d|i} \mu^3(p) \sum_{e|q} \mu(e)\mu^2\left(\frac {q}{e}\right) \\ = & \sum_{i=1}^n \sum_{d|i} \mu(p) \sum_{e|q} \mu(e) \qquad & (有值的 q 一定无平方因子) \\ = & \sum_{i=1}^n \sum_{d|i} \mu(p) [q = 1] \\ = & \sum_{i=1}^n \sum_{p^2|i} \mu(p) \\ = & \sum_{p = 1}^{\left\lfloor\sqrt n\right\rfloor } \mu(p)\left\lfloor\frac n{p^2} \right\rfloor \end{aligned} \]这部分的复杂度是 \(O(\sqrt n)\) 的。加上求质数个数的复杂度是亚线性的。可过。
标签：right,18,质数,mu,22.12,text,闲话,sum,left From： https://www.cnblogs.com/joke3579/p/chitchat221218.html