hdu 2204 Eddy's爱好 容斥原理

本文主要是介绍hdu 2204 Eddy's爱好 容斥原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个正整数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<stdio.h>
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
LL n;
LL dfs(LL x,LL y,int idx,int flag)
{if(flag >= 3) return 0;LL ret = 0;for(int i = idx; i < 17; ++i)ret += (LL)(pow(x,1.0/prime[i]/y)+eps) - 1 - dfs(x,y*prime[i],i+1,flag+1);return ret;
}
int main()
{while(~scanf("%I64d",&n)){printf("%I64d\n",dfs(n,1,0,0)+1);}
}

这篇关于hdu 2204 Eddy's爱好 容斥原理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---