BZOJ 2240 – 完全平方数

题目链接:BZOJ 2240

要求寻找$\sum_{i=1}^{n} \mu^2(i) = k$的最小$n$。

根据莫比乌斯系数容斥

$$\sum_{i=1}^{n} \mu^2(i) = \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu^2(i) \lfloor \frac{n}{i^2} \rfloor $$

我们可以$O(\sqrt{n})$地求小于等于$n$的无平方因子数的个数,接着二分即可,时间复杂度$O(T \sqrt{k} \log k)$。

 

说点什么

avatar
50
  Subscribe  
提醒