Eddy's爱好(容斥原理)

2017年07月23日 9点热度 0人点赞 0条评论

Eddy's爱好

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2579    Accepted Submission(s): 1194

Problem Description
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


/*首先是范围1~1e18,2的60次方正好比它大点,所以说最多开到60次方
然后一个数一定是由素数相乘得到,而2的2次方其实包含2的4次方,所以指数只要管素数的乘即可
所以用容斥原理即可 
*/ 
#include
#include
#include
using namespace std;
#define ll long long
int p[]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll ans,n;
void dfs(int cur,int s,int cnt)
{
    ll t=(ll)pow(n,1.0/s);
    if(t>1)
    {
        if(cnt&1) ans+=t-1;
        else ans-=t-1;
    }
    if(cnt>2) return;//剪枝
    for(int i=cur+1; i<17; ++i)
        dfs(i,s*p[i],cnt+1);
}
int main()
{
    while(cin>>n)
    {
        ans=1;//这个细节要处理好,1不满足容斥原理
        for(int i=0; i<17; ++i) //枚举起点
            dfs(i,p[i],1);
        cout<
未经允许不得转载!Eddy's爱好(容斥原理)

update

纸上得来终觉浅, 绝知此事须躬行。