HDU2204 Eddy's爱好

题意：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。

解析：一个数N 开K次根后得到M  则小于M的所有数的K次方一定小于N

因为任何一个合数都能分解为素数的乘积 所以用素数即可

2^60>10^18所以，指数最大为60，打表60以内的素数。因为2*3*5*7大于60，所以最多只有三个数相乘，即三个集合相交。

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
LL ans,n;
int i;
int prime[]={,,,,,,,,,,,,,,,,};
void dfs(int j,int num,int p)
{
    if(p == )
    {
        LL t = pow(n,1.0/num);
        t--;                    // 因为每次都有底数为1的情况 所以每次都要减1 最后输出时加1
        if(t > )
            ans += t*(i&?:(-));  //容斥定理 奇数个集合时为正 偶数个集合时为负
        return;
    }
    if(j >= ) return;  //prime里的下标最大为17
    if(num * prime[j] < )
        dfs(j+,num*prime[j],p-);  //要本次的prime[j] 递归找下一个要的
    dfs(j+,num,p);       //不要本次的prime[j]  递归找要的
}int main()
{
    while(cin>>n)
    {
        ans = ;
        for(i=;i<=;i++)   //如果把prime里的每一个数看作一个集合 则这个循环为枚举集合的个数
            dfs(,,i);
        cout<<ans + <<endl;   // 加上底数为1的情况    }
    return ;
}