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
Sample Output
4
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，所以只要枚举到三即可
-----------------------------
就是对指数进行容斥。
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 using namespace std; 7 typedef long long LL; 8 int prime[18]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59}; 9 LL res, n; 10 int a[5]; 11 void dfs(int cur, int num, int cnt, LL sum) // 从素数表cur位置开始，当前一共num个，需要cnt个，当前素数乘积为sum 12 { 13 if (num == cnt) 14 { 15 LL temp = (LL) pow(n + 0.5, 1.0 / sum); 16 if (temp > 1) 17 res += temp - 1; // 减去1的情况 18 return; 19 } 20 for (int i = cur; i < 17; i++) 21 { 22 if (sum * prime[i] < 60) //如果素数没到60，则这个素数可以取 23 { 24 dfs(i + 1, num + 1, cnt, sum * prime[i]); 25 } 26 else // 否则跳过该数 27 { 28 dfs(i + 1, num, cnt, sum); 29 } 30 } 31 } 32 int main() 33 { 34 while (scanf("%I64d", &n) != EOF) 35 { 36 LL sum = 0; 37 for (int i = 1; i <= 3; i++) 38 { 39 res = 0; 40 dfs(0, 0, i, 1); 41 if (i & 1) 42 sum += res; 43 else 44 sum -= res; 45 } 46 printf("%I64d ", sum + 1); 47 } 48 return 0; 49 }