Eddy's爱好
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
Ignatius 喜欢收集蝴蝶标本和邮票，但是Eddy的爱好很特别，他对数字比较感兴趣，他曾经一度沉迷于素数，而现在他对于一些新的特殊数比较有兴趣。
这些特殊数是这样的：这些数都能表示成M^K，M和K是正整数且K>1。
正当他再度沉迷的时候，他发现不知道什么时候才能知道这样的数字的数量，因此他又求助于你这位聪明的程序员，请你帮他用程序解决这个问题。
为了简化，问题是这样的：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。
这些特殊数是这样的：这些数都能表示成M^K，M和K是正整数且K>1。
正当他再度沉迷的时候，他发现不知道什么时候才能知道这样的数字的数量，因此他又求助于你这位聪明的程序员，请你帮他用程序解决这个问题。
为了简化，问题是这样的：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。
Input
本题有多组测试数据，每组包含一个整数N，1<=N<=1000000000000000000(10^18).
Output
对于每组输入，请输出在在1到N之间形式如M^K的数的总数。
每组输出占一行。
每组输出占一行。
Sample Input
10
36
1000000000000000000
36
1000000000000000000
Sample Output
4
9
1001003332
9
1001003332
题意：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。
思路：我们可以由n^(1/p)，知道指数为p的有多少个数。
通过观察，可以发现若一个数可以表示成x^(k*t)，则可以表示成(x^k)^t。因此指数必然为素数。
枚举素数便可以得到指数为p的个数，但是可能出现重复，例如：x^3=y^5，其中x=t^5，y=t^3。
运用容斥原理，设a[i]表示指数为第i个素数的个数，那么答案等于满足一个的，减去两个的，加上三个的……
由于2^60>10^18，2*3*5*7>60，所以只要枚举到三即可
-----------------------------
就是对指数进行容斥。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
int prime[]={, , , , , , , , , , , , , , , , };
LL res, n;
int a[];
void dfs(int cur, int num, int cnt, LL sum) // 从素数表cur位置开始，当前一共num个，需要cnt个，当前素数乘积为sum
{
if (num == cnt)
{
LL temp = (LL) pow(n + 0.5, 1.0 / sum);
if (temp > )
res += temp - ; // 减去1的情况
return;
}
for (int i = cur; i < ; i++)
{
if (sum * prime[i] < ) //如果素数没到60，则这个素数可以取
{
dfs(i + , num + , cnt, sum * prime[i]);
}
else // 否则跳过该数
{
dfs(i + , num, cnt, sum);
}
}
}
int main()
{
while (scanf("%I64d", &n) != EOF)
{
LL sum = ;
for (int i = ; i <= ; i++)
{
res = ;
dfs(, , i, );
if (i & )
sum += res;
else
sum -= res;
}
printf("%I64d\n", sum + );
}
return ;
}