前一部分见 UOJ Long Round #1 题解

枚举$x$，考虑如何快速计算$f(m,x)$。

因为有值的位置都是$x$的倍数那么不妨将$x$除掉，令$q_x(i)$为除掉$x$后$i$位置的值，容易知道$q_x(i)=q(ix)[x|f(ix)]=q(i)[x|f(ix)]$。

不难发现$q_x$其实是积性函数，所以只用看质数正次幂位置的值。

那么有$q_x(p^e)=[p|x][e\bmod 2=0]p^{ce/2}+[p\nmid x]p^{c\lfloor e/2\rfloor}$。

对于比原来的函数$q(p^e)=p^{c\lfloor e/2 \rfloor}$，由于在不整除$x$的位置一样，所以不妨算出$q_x/q$，其中除法是Dirichlet除法。

令$g_x=q_x/q$，容易得到$g_x(p^e)=[p|x](-1)^e$。

那么就有$f(m,x)=\sum_{i=1}^{m/x}q_x(i)=\sum_{i=1}^{m/x}g_x(i)Sq(m/(ix))$，其中$Sq(m)=\sum_{i=1}^mq(i)$，写个搜索发现$g$有值的位置不多，$n=5\times 10^5,m=1.2\times 10^{11}$时大约$2.4\times 10^7$个位置有值。

问题就转变成预处理所有$Sq(m/x)$。

熟悉powerful number的选手都知道，令$h=q/I$，其中$I(p^e)=1$，$h(p)=0$，所以$h$只有powerful number位置有值。

但是由于这题的特殊性，$h(p^e)=[e\bmod 2=0]p^{ce/2}-p^{c(e/2-1)}$，也就是只有$a^2$位置有值，那么令$h_2(i)=h(i^2)$。

首先线性筛处理出前面$\lfloor \sqrt{m}\rfloor$的$h_2(i)$，复杂度$O(\sqrt{m}+\pi(\sqrt{m})\log c)$。

那么有$Sq(m)=\sum_{i=1}^{\lfloor\sqrt{m}\rfloor}h_2(i)\lfloor \frac{m}{i^2}\rfloor$。

• 对于$i\le m^{1/3}$的部分直接计算；
• 对于$i>m^{1/3}$的部分$\lfloor \frac{m}{i^2}\rfloor$只有$m^{1/3}$个值，那么枚举每个值算出对应的范围即可。

所以计算一个$Sq(m)$的复杂度是$O(m^{1/3})$。

设阈值为$S$。

• 对于前$S$个前面和通过线性筛算出前$S$个$q$，复杂度$O(S)$；
• 对于$m/x>S$用上述方法计算，处理的这一部分的复杂度为$O(\sum_{i=1}^{m/S}(m/i)^{1/3})=O(m/S^{2/3})$。

当$S=m^{3/5}$时复杂度最优，那么预处理所有$Sq(m/x)$的复杂度为$O(m^{3/5})$。

实际得分：100。