hdu 2204 Eddy's爱好

// 一个整数N，1<=N<=1000000000000000000(10^18).
// 输出在在1到N之间形式如M^K的数的总数
// 容斥原理
// 枚举k=集合{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59}中选取1或多个数乘积的值 
而且大于三个质数的乘积就大于60 而2^60>10^18 所以最多只取3个素数

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxm 100010
#define maxn 1000110
int prim[110]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};// 17个
int main()
{
    int i,j,ct,mid;
    int rc[5];
    __int64 n,m,ans,tp;
    while(scanf("%I64d",&n)!=EOF){
        ans=0;
        // if(n<4) { printf("%d
",1);continue;}
        int x=(1<<17)-1;
        for(i=1;i<=x;i++){
            mid=i;
            ct=j=0;
            while(mid){
                if(mid&1) rc[ct++]=j;
                j++;
                if(ct>3) break;
                mid=mid>>1;
            }
            if(ct>3) continue;
            tp=1;
            for(j=0;j<ct;j++)
                tp=tp*prim[rc[j]];
            if(tp>=60) continue;
            m=pow(n+1.0,1.0/tp);
            m++;
            while(pow(m,0.0+tp)>n) m--;
            if(ct%2) ans+=(m-1);
            else ans-=(m-1);
        }
         printf("%I64d
",ans+1);
    }
    return 0;
}