题意分析

我们要计算 $1 < p \le n$ 的质数 $p$ 中，二进制表示末两位为 $01$ 的个数。

二进制末两位为 $01$ 意味着： $p \bmod 4 = 1$ 因为：

• 末位 1 表示 $p$ 是奇数
• 倒数第二位 0 表示 $p \bmod 4 = 1$

所以问题转化为：计算不超过 $n$ 的质数中，模 $4$ 余 $1$ 的个数。

---

模 4 余 1 的质数分布

除了 $2$ 以外，所有质数都是奇数，所以模 $4$ 只能是 $1$ 或 $3$。

• 模 $4$ 余 1 的质数：$5, 13, 17, 29, \dots$
• 模 $4$ 余 3 的质数：$3, 7, 11, 19, 23, \dots$

注意 $2$ 是特殊情况，但题目要求 $p>1$，且 $2$ 的二进制是 $10$，末两位 $10$ 不符合 $01$，所以 $2$ 不计算在内。

---

算法选择

$n \le 3\times 10^{10}$ 很大，需要高效的质数计数算法。

1. 小范围 ($n \le 10^7$)

可以用埃拉托色尼筛法，直接筛出所有质数，然后统计模 $4$ 余 $1$ 的个数。

复杂度 $O(n \log \log n)$，空间 $O(n)$。

---

2. 大范围 ($n \le 3\times 10^{10}$)

需要用亚线性质数计数法，如：

• Meissel-Lehmer 算法
• Lucy_Hedgehog 筛法（动态规划质数计数）
• 洲阁筛 / Min_25 筛

这里我们选择 Lucy_Hedgehog 方法（也称为“数论分块 + DP”质数计数），它可以方便地统计模 $4$ 余 $1$ 和余 $3$ 的质数个数。

---

Lucy_Hedgehog 方法思路

设 $S(v, p)$ 表示 $[2, v]$ 中最小质因子 $\ge p$ 的数的个数（或某种属性之和）。

我们想分别计算：

• $f_1(n)$ = 模 $4$ 余 $1$ 的质数个数
• $f_3(n)$ = 模 $4$ 余 $3$ 的质数个数

初始时，$S(v, 2)$ 表示 $[2, v]$ 中所有奇数个数（因为最小质因子 $\ge 2$ 就是所有 $\ge 2$ 的数，但要考虑模 4 分类）。

更直接的方法是：
用 DP 计算 $g(v, k)$ = $[2, v]$ 中质数或最小质因子 $> p_k$ 的数的个数（$p_k$ 是第 $k$ 个质数）。

然后利用： $\pi(n) = g(n, \infty)$ 我们可以修改状态，同时记录模 $4$ 余 $1$ 和余 $3$ 的计数。

---

具体实现方案

我们维护两个数组：

• $g_1[v]$ = $[2, v]$ 中模 $4$ 余 $1$ 的质数或最小质因子 $> p_k$ 的数的个数
• $g_3[v]$ = $[2, v]$ 中模 $4$ 余 $3$ 的质数或最小质因子 $> p_k$ 的数的个数

初始时（$k=0$，即最小质因子 $\ge 2$）：

• 对于 $v \ge 1$，$g_1[v] = \lfloor (v+3)/4 \rfloor$（模 4 余 1 的整数个数，从 1 开始算，但要去掉 1）
• 对于 $v \ge 3$，$g_3[v] = \lfloor (v+1)/4 \rfloor$（模 4 余 3 的整数个数）

然后从小到大枚举质数 $p$ 进行筛除：

• 如果 $p \equiv 1 \pmod{4}$，筛的时候会影响 $g_1$ 和 $g_3$ 的分布
• 如果 $p \equiv 3 \pmod{4}$，同理

转移公式： $ g_j[v] \leftarrow g_j[v] - \left( g_{j\cdot p \bmod 4}\left[ \frac{v}{p} \right] - g_{j\cdot p \bmod 4}[p-1] \right) $ 这里 $j$ 是当前考虑的余数类（1 或 3），$j\cdot p \bmod 4$ 是乘 $p$ 后的余数类。

---

算法步骤

1. 预处理 $\sqrt{n}$ 以内的质数。
2. 初始化 $g_1, g_3$ 为初始计数（去掉 1，保留质数和合数）。
3. 对每个质数 $p \le \sqrt{n}$，从大到小更新 $g_1, g_3$（数论分块枚举 $v$）。
4. 最终 $g_1[n]$ 就是模 $4$ 余 $1$ 的质数个数（因为所有合数被筛掉，只剩质数）。

---

样例验证

样例 1：$n=20$

模 $4$ 余 $1$ 的质数：$5, 13, 17$，共 $3$ 个，输出 $3$。

样例 2：$n=100000$

输出 $4783$。

---

复杂度

• 时间复杂度：$O(n^{3/4} / \log n)$
• 空间复杂度：$O(\sqrt{n})$
• 可处理 $n \le 10^{12}$ 级别

---

总结

这道题本质是模 4 余 1 的质数计数问题，通过将二进制末两位条件转化为模 $4$ 条件，再利用高效的亚线性质数计数算法（如 Lucy_Hedgehog 法）求解，可以处理 $n$ 高达 $3\times 10^{10}$ 的情况。