hdu2204 Eddy's爱好 打表+容斥原理

Ignatius 喜欢收集蝴蝶标本和邮票，但是Eddy的爱好很特别，他对数字比较感兴趣，他曾经一度沉迷于素数，而现在他对于一些新的特殊数比较有兴趣。
这些特殊数是这样的：这些数都能表示成M^K，M和K是正整数且K>1。
正当他再度沉迷的时候，他发现不知道什么时候才能知道这样的数字的数量，因此他又求助于你这位聪明的程序员，请你帮他用程序解决这个问题。
为了简化，问题是这样的：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。

打表+容斥原理

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
const int pnum=36;
const double eps=1e-8;

int num[40]={0,
    2,3,5,6,7,
    10,11,13,14,15,
    17,19,21,22,23,
    26,29,30,31,33,
    34,35,37,38,39,
    41,42,43,46,47,
    51,53,55,57,58,
    59};
int bit[40]={0,
    1,1,1,2,1,
    2,1,1,2,2,
    1,1,2,2,1,
    2,1,3,1,2,
    2,2,1,2,2,
    1,3,1,2,1,
    2,1,2,2,2,
    1};
int high[40]={0,
    1000000000,1000000,3981,1000,372,
    63,43,24,19,15,
    13,8,7,6,6,
    4,4,3,3,3,
    3,3,3,2,2,
    2,2,2,2,2,
    2,2,2,2,2,
    2};

ll n;

ll QP(ll a,int i){
    ll ans=1,tmp=a;
    while(i){
        if(i&1)ans*=tmp;
        tmp*=tmp;
        i>>=1;
    }
    return ans;
}

int check(int i){
    int l=1,r=high[i];
    while(l<=r){
        int m=l+((r-l)>>1);
        ll res=QP(m,num[i]);
    //    printf("%d %d %d %lld
",l,r,m,res);
        if(res<=n)l=m+1;
        else r=m-1;
    }
    return r-1;
}

int main(){
//    n=9;
//    printf("%d
",check(1));
    while(scanf("%lld",&n)!=EOF){
        ll ans=1;
        for(int i=1;i<=pnum;++i){
//            printf("%d
",check(i));
            if(bit[i]%2)ans+=check(i);
            else ans-=check(i);
        }
        printf("%lld
",ans);
    }
    return 0;
}