题意：完全平方数是指含有平方数因子的数。求第ki个非完全平方数。 解法：比较明显的二分，getsum(int middle)求1-middle有多少个非完全平方数，然后二分。求1-middle的非完全平方数个数可以用总数减掉完全平方数个数。计算完全平方数的个数用容斥：     首先加上n/(2*2)+n/(3*3)+n/(5*5)+n/(7*7)...+...然后减掉出现两次的

题意：全然平方数是指含有平方数因子的数。求第ki个非全然平方数。 解法：比較明显的二分，getsum(int middle)求1-middle有多少个非全然平方数，然后二分。求1-middle的非全然平方数个数能够用总数减掉全然平方数个数。计算全然平方数的个数用容斥：     首先加上n/(2*2)+n/(3*3)+n/(5*5)+n/(7*7)...+...然后减掉出现两次的，然后加上三次

题解： 显然可以二分， O(logn) O(log n) 的代价二分答案，问题转换为 [1, x] 中有多少个无平方因子数 由容斥原理，[1, x] 中无平方因子数等于： • 0 个质数乘积的平方的倍数个数 • - 1 个质数乘积的平方的倍数个数 • + 2 个质数乘积的平方的倍数的个数 • …… 枚举 [1,sqrt(x)] [1, sqrt(x)] 范围内的数，把 μ(i)∗