Eddy's爱好

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 9 Accepted Submission(s) : 6

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

Author

Eddy

——————————————————————————————————

思路：按指数k进行分，排除底数为1的情况指数肯定不大于64，这64个数里的质数有18

个，对这些数进行任意组合成x判断？^x<=n ？的个数，在利用容斥原理计数。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <algorithm>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <cmath>

using namespace std;

#define LL long long

const int inf=0x7fffffff;

const double eps = 1e-7;

int a[18]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};

LL n;

int ans;

LL mypow(LL x,LL y)

{

    LL ans=1;

    for(int i=1; i<=y; i++)

        ans*=x;

    return ans;

}

void dfs(int pos,int x,int cnt)

{

    double xx=log(n)/log(2);

    if(x>xx)

        return;

    if(pos>=18)

    {

        if(cnt==0)

            return;

        if(cnt%2)

        {

            ans=ans+(int)(pow(n,1.0/x)+eps)-1;

        }

        else

            ans=ans-(int)(pow(n,1.0/x)+eps)+1;

        return;

    }

    dfs(pos+1,x*a[pos],cnt+1);

    dfs(pos+1,x,cnt);

}

int main()

{

    while(~scanf("%lld",&n))

    {

        ans=0;

        dfs(0,1,0);

        printf("%d\n",ans+1);

    }

    return 0;

}