多校第一場 1010 hdu 5297 Y sequence(容斥+二分)

題目連結：

點選打開連結

題目大意：

給出一個序列，序列中的每一個數都不是數列中其他數的幂，問序列中的第n個數的值

題目分析”：

首先要找出如果能夠知道num之前的數有多少個存在于數列Y中，那麼我們很容易就可以利用二分得到答案，那麼我們定義f(n)=前n個自然數當中在Y序列中的數的個數。

那麼f(n)應該怎麼做呢，sqrt(n)就是在二次方情況下需要抹去的數的個數，依次類推，我們能夠得到r次方以内的分别得到需要抹去的數的個數，但是需要注意的是這些數當中會有重複的，而且每個質數，會把隻包含它的合數全部重複，是以我們隻統計質數幂的情況，然後利用容斥定理排除質數中的重複的情況，得到f(n)

然後進行二分即可。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <cmath>

using namespace std;

int p[]={-2,-3,-5,-7,-11,-13,-17,-19,-23,-29,-31,-37,-41,-43,-47,-53,-59,-61,-67};

typedef long long LL;

int r,t;
LL n;
vector<int> cal;

void init ( )
{
    cal.clear();
    for ( int i = 0 ; abs(p[i]) <= r ;i++ )
    {
        int len = cal.size();
        for ( int j = 0 ; j < len ; j++ )
        {
            if ( abs(cal[j]*p[i]) < 64 )
                cal.push_back ( p[i]*cal[j] );
        }
         cal.push_back( p[i] );
    }
}

LL get ( LL x )
{
    if ( x == 1 ) return 0;
    LL ans = x;
    for ( int i = 0 ; i < cal.size () ; i++ )
    {
        LL temp = (LL)( pow ( x+0.5 , 1.0/(abs(cal[i])) )-1);
        if ( cal[i] < 0 )
            ans -= temp;
        else
            ans += temp;
    }
    return ans - 1;
}

/*LL ans ( )
{
    init ( );
    LL a = n;
    while (1)
    {
        LL temp = get ( a );
        //cout << a << " " << temp << endl;
        if ( temp == n ) break;
        a += n - temp;
    }
    return a;
}*/

LL ans ( )
{
    init ();
    LL l = 1 , r = 1e18 , mid;
    while ( l != r )
    {
        mid = l + r >>1;
        if ( get(mid) >= n ) r = mid;
        else  l = mid+1;
    }
    return l;
}


int main ( )
{
    scanf ( "%d" , &t );
    while ( t-- )
    {
        scanf ( "%I64d%d" , &n , &r );
        printf ( "%I64d\n" , ans () );
    }
}