hdu 2204 Eddy's爱好 容斥原理

Eddy's爱好

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

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

 

Author

Eddy

思路：根据指数找个数，由于n^6=(n^2)^3=(n^3)^2;容斥解决

　　　比如：10以内的二次方；sqrt（10）=3个；注意精度。。。

　　　涨知识:求根号，pow（n，1.0/m);

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000007

#define inf 999999999

#define pi 4*atan(1)

//#pragma comment(linker, "/STACK:102400000,102400000")

ll p[]={,,,,,,,,,,,,,,,,},ans;

ll gcd(ll x,ll y)

{

    return y==?x:gcd(y,x%y);

}

void dfs(ll lcm,ll pos,ll step,ll x)

{

    if(lcm>)

    return;

    if(pos==)

    {

        if(step==)

        return;

        ll temp=(ll)pow(x,1.0/lcm+1e-);

        if(step&)

        ans+=temp-;

        else

        ans-=temp-;

        return;

    }

    dfs(lcm,pos+,step,x);

    dfs(lcm/gcd(p[pos],lcm)*p[pos],pos+,step+,x);

}

int main()

{

    ll x,y,z,i,t;

    while(~scanf("%I64d",&x))

    {

        ans=;

        dfs(,,,x);

        printf("%I64d\n",ans+);

    }

    return ;

}