传送门
Ignatius 喜欢收集蝴蝶标本和邮票，但是Eddy的爱好很特别，他对数字比较感兴趣，他曾经一度沉迷于素数，而现在他对于一些新的特殊数比较有兴趣。
这些特殊数是这样的：这些数都能表示成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

题解

容斥水题
pow(x,1.0/n)可以求出从1到x中有几个可以表示成(a^n)的个数，比如pow(16,1.0/2)=4,即 1,2,4,16，然后就是能被开3次方的也能被开6次方，能被开2次方的也能被开2，4，6…次方，如果n从1开始枚举会造成同一个数被多次计算。这时就想到，如果一个数可以被表示成M^K的话，K可以表示成一些素数的乘积那么，只需要计算为素数的n即可，但还不够，此时用到容斥因为235*7>60，只需要容斥三次即可（ans=所有能被开单个素数的-能被开两个素数的乘积+能被开三个素数的乘积）

#include<iostream>
#include<cmath>
using namespace std;

int a[50]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
int i,j,k;
long long x;
int main()
{
	while(cin >> x)
	{
		long long temp = 0,ans = 1;
		for( i=0;;i++)
		{
			temp = (long long)(pow(x,1.0/a[i]));
			if(temp<2)
				break;
			ans+=temp -1;
			for( j=i+1;;j++)
			{
				temp = (long long)(pow(x,1.0/(a[i]*a[j])));
				if(temp<2)
					break;
				ans-=temp-1;
	
				for( k=j+1;;k++ )
				{
					temp = (long long)(pow(x,1.0/(a[i]*a[j]*a[k])));
					if(temp<2)
						break;
					ans+=temp-1;
				}
			}
		}	
		cout << ans << endl;
	}	
	
	return 0;
 }