标签： 数论

（其实一开始想的是错的，实际上就是mu[i]^2的前缀和S

先考虑对立面，2到n之间有多少个数可以被平方数整除？可以枚举从2到sqrt(n)，然后把可以被这些数字的平方整除的算上，也就是n/(i^2)个对于每个来说。但是这里会有重复的，比如i分别为2，3，6时，算上了4，9，36，其中36被算了两遍，所以要加加减减。（好吧其实我也还没自己证明出来但是今天有点疲回头填坑ooorz
继续阅读“[暑期集训][数学][数论][组合数学] SPOJ Square-free integers”