预备

定义1

Powerful Number,定义为对于一个整数 $n$，满足它的任何一个质因子都至少有两个，也就是 $n=\prod p_i^{c_i}$，满足 $\forall c_i > 1$，下文简化为 $PN$ 数。

引理1

对于每一个 $PN$ 数，它都可以表示成 $a^2b^3$ 的形式

引理2

$[1,n]$ 范围以内的数的 $PN$ 数个数为 $O(\sqrt{n})$。

证明

根据引理1，先枚举 $a$，再枚举 $b$。

$\int_{1}^{\sqrt{n}} {\sqrt[3]{\frac{n}{x^2}}\mathrm{d}x}=O(\sqrt{n})$

PN 筛

假如现在给你一个积性函数 $f$，要你求出 $f$ 的前 $n$ 项之和，其中 $n\leq 10^{10}$。

$PN$ 筛是这么做的，构造积性函数 $g$，这个函数满足，易求前缀和，且对于质数 $p$，满足 $f(p)=g(p)$。

设 $h=f/g$，$f=g*h$，根据狄利克雷卷积的运算法则，$h$ 也是积性函数，$h(1)=1$。

$f(p)=g(1)h(p)+h(1)g(p)=g(p)$，$h(p)=0$，由此所有非 $PN$ 数，$h$ 都是 $0$。

$$F(n)=\sum_{i=1}^n f(i) =\sum_{i=1}^n \sum_{d|i} h(d)g(\frac{i}{d}) =\sum_{d=1}^n h(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} g(i) =\sum_{d=1}^n h(d)G(\lfloor\frac{n}{d}\rfloor) =\sum_{d\in PN} h(d)G(\lfloor\frac{n}{d}\rfloor) $$

$h$ 函数由于是积性函数，所以只要计算 $h(p^c)$，一种方法是 dp 预处理，另一种是推式子求公式。

根据引理2，我们搜索所有 $PN$ 数，然后从小到大枚举每个质数的指数，这个搜索构成一个树形结构，如果一个数 $d$ 乘以 $p^2$ 后就大于 $n$ 了，这意味着以后也不肯能再变化了，那么直接剪枝。于是每个节点要么有至少两个儿子，要么是叶节点，总结点数为 $O(\sqrt{n})$。

以上就是 PN 筛的全过程，求 $G$ 时可能需要杜教筛辅助，总复杂度 $O(\sqrt{n})$。