HDOJ2204

每天都来补题确实很充实，类型都不一样

大概思路都会，就是写不对的题，才会目前来说最重要最有意义的题了吧

http://acm.hdu.edu.cn/showproblem.php?pid=2204

给定n，求1-n中有多少个可以表示成M的K次方的数。K>1

题意很简单，但是怎么想？题面上说到了素数，第一想法就是K从素数开始枚举！

当K不是素数时，必然是重复算过的！比如K=6时，一定会有一个（M1的2次方）的3次方=（M2的3次方）的2次方

那么，最大素数是多少？n最大值是1e18，所以呢，找到一个x，使得2的x次方大于n的最大值，x=60

所以取61为最大素数肯定满足条件了

可以枚举了？

还是要注意容斥！

例如15=3*5，所以，3的要加，5的要加，15的要减

最多是几层？

2*3*5=30

2*3*5*7=210已经大于60了，所以最多枚举三重循环就好

现在是有了n和K，怎么得到M呢？

只需要这一行代码：

tmp=(int)(pow((double)n,1.0/prime[i])+eps);

所以，注意：一开始ans赋初始化就为1，之后，所有的计算把1除掉就好

代码：

bool p[maxn];
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int all=25;

int main(){
	//input;
	long long n;
	int i,j,k,ans,tmp;
	while(scanf("%I64d",&n)!=EOF){
		ans=1;
		for(i=0;i<all;i++){
			tmp=(int)(pow((double)n,1.0/prime[i])+eps);
			ans+=tmp-1;
		}
		for(i=0;i<all;i++)
			for(j=i+1;j<all;j++){
				tmp=(int)(pow((double)n,1.0/(prime[i]*prime[j]))+eps);
				ans-=tmp-1;
			}
		for(i=0;i<all;i++)
			for(j=i+1;j<all;j++)
				for(k=j+1;k<all;k++){
					tmp=(int)(pow((double)n,1.0/(prime[i]*prime[j]*prime[k]))+eps);
					ans+=tmp-1;
				}
		printf("%d\n",ans);
	}
	return 0;
}