BZOJ-2440: [中山市选2011]完全平方数(二分+莫比

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2440

首先直接求不好求，考虑二分，那么就是求[1..mid]里符合条件的数有几个，首先可以很简单的想到容斥，不过略麻烦，所以可以直接用莫比乌斯函数求掉。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

 

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 = 0 ;

        for ( ll i = 1 ; i <= ret ; ++ i ) rec += ll( u[ i ] * n / ( i * i ) ) ;

        return rec ;

}

 

inline ll solve( ll k ) {

        ll l = 0 , r = k << 2 , mid ;

        while ( r - l > 1 ) {

                mid = ( l + r ) >> 1 ;

                if ( cal( mid ) < ll( k ) ) l = mid ; else r = mid ;

        }

        return r ;

}

 

int main(  ) {

        Init(  ) ;

        ll T ; scanf( "%lld" , &T ) ;

        while ( T -- ) {

                ll k ; scanf( "%lld" , &k ) ;

                printf( "%lld\n" , solve( k ) ) ;

        }

        return 0 ;

}