查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转题意:求第$k$个没有完全平方数因子的数可以发现答案具有单调性,可以二分答案,然后判断$[1,n]$中满足条件的个数是否为$k$这个结果为$1$($0$个平方因子)的倍数-【$4,9,16,25,...$】($1$个平方因子)的倍数+【$36,100,...$】($2$个平方因子)的倍数...也就是:$$\sum_{i=1}^{i^2\le n} \mu(i)\left \lfloor \frac n{i^2}\right \rfloor$$这样的话只需要线性筛到$\sqrt{10^9}\le 40……