上周尝试把这道水题加强了一下，变成了这个命题，那么：

请问求解这个命题的最优时间复杂度是多少？

因为我太逊，所以目前我只知道通过很水的【莫比乌斯反演+欧拉筛 $\mu$+扩展欧拉降幂+整除分块+杜教筛】能做到 $\Theta(n^\frac{3}{4}+p^\frac{1}{2}+n^\frac{1}{2}\log\varphi(p))$，如果使用【Pollard-Rho】可以进一步优化到 $\Theta(n^\frac{3}{4}+p^\frac{1}{4}\log(p)+n^\frac{1}{2}\log\varphi(p))$

违规紫衫