小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。 这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。 然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？ Input包含多组测试数据。文件第一行有一个整数 T，表示测试
数据的组数。 第2 至第T+1 行每行有一个整数Ki，描述一组数据，含义如题目中所描述。 Output含T 行，分别对每组数据作出回答。第 i 行输出相应的
第Ki 个不是完全平方数的正整数倍的数。 Sample Input4 1 13 100 1234567Sample Output1 19 163 2030745 Hint
对于 100%的数据有 1 ≤ Ki ≤ 10^9
, T ≤ 50
SOLUTION:
首先二分答案 问题转化为求x以内有多少个无平方因子数
根据容斥原理可知 对于√x以内的所有质数 x以内的无平方因子数=无需是任何质数的倍数的数的数量(即x)-是至少一个质数平方倍数的数的数量+是至少两个质数平方倍数的数的数量-是至少三个质数平方倍数的数的数量...
我们回去考虑莫比乌斯函数，我们发现每一个质数乘积的符号与莫比乌斯函数的符号恰好吻合！
因此我没把原先2^k复杂度的容斥变成了o（n） 的容斥
CODE:
#include#include #include #include using namespace std ;typedef long long ll ;const ll maxn = 100000 ;bool f[ maxn + 10 ] ;ll u[ maxn + 10 ] ;inline void Init( ) { memset( f , true , sizeof( f ) ) ; f[ 1 ] = false , u[ 1 ] = 1 ; for ( ll i = 2 ; i <= maxn ; ++ i ) if ( f[ i ] ) { u[ i ] = -1 ; for ( ll j = i << 1 ; j <= maxn ; j += i ) { f[ j ] = false ; if ( ( j / i ) % i ) u[ j ] = - u[ j / i ] ; else u[ j ] = 0 ; } }}inline ll cal( ll n ) { ll ret = ll( sqrt( n ) ) ; ll rec = n ; for ( ll i = 2 ; i <= ret ; ++ i ) rec += ll( u[ i ] * n / ( i * i ) ) ; return rec ;}inline ll solve( ll k ) { ll l = 0 , r = k << 2 , mid ; ll ans; /* while ( r - l > 1 ) { mid = ( l + r ) >> 1 ; if ( cal( mid ) < ll( k ) ) l = mid ; else r = mid ; }*/ while(l<=r) { mid = l+r>>1; if(cal(mid)>=k)ans=mid,r=mid-1; else l=mid+1; } return ans;}int main( ) { Init( ) ; ll T ; scanf( "%lld" , &T ) ; while ( T -- ) { ll k ; scanf( "%lld" , &k ) ; printf( "%lld\n" , solve( k ) ) ; } return 0 ;}