HDU

题意：求(1 - N(1le N le 1e18))中，能表示成(M^k(M>0,k>1))的数的个数
分析：正整数p可以表示成(p = m^k = m^{r*k'})的形式，其中k'为素数。枚举幂k，求出满足(p^kle N)的最大的(p),则对于当前的(k),任意小于(p)的正整数(p')，都有(p'^{k}<N)，因此在(1-N)范围内有(N^{frac{1}{k}})个满足条件的数。
因为(2^{60}>10^{18})，所以枚举到的k'最多不超过60，预处理出60以内的所有素数。
又(2*3*5=30,2*3*5*7=210>60)，所以最多只考虑3个素幂次相乘的情况。
但是如此枚举会出现重复的情况，例如((2^{3})^{2} = (2^{2})^{3} = 2^6)在枚举(k=2)和(k=3)时重复了，根据容斥的思想，枚举到偶数个素幂次相乘时，减去该结果。
*注意每次计算(N^{frac{1}{k}})时，减去1的情况，最后将结果加1，因为1在每种情况中都会出现，不必重复。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
const LL prime[20]  ={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
const int len = 17;
const double eps  =1e-8;
LL ans;
LL N;

void dfs(int pos,int num,int tot,LL k = 1)
{
    if(k>60) return;
    if(num==tot){
        LL p = (LL)(pow(N,1.0/(0.0+k))+eps)-1;
        ans +=p;
        return;    
    }
    if(pos==len) return;
    dfs(pos+1,num,tot,k);
    dfs(pos+1,num+1,tot,k*prime[pos]);
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    while(scanf("%lld",&N)==1){
        LL res= 0;
        for(int i =1;i<=3;++i){
            ans=0;
            dfs(0,0,i);
            if(i&1) res+=ans;
            else res-=ans;
        }
        res+=1;
        printf("%lld
",res);
    }
    return 0;
}