hdu 2205（容斥原理）

Eddy's爱好

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

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

 这个是看别人的才有点明白  但自己给出了自己理解的思路

m^k次方 假如k是不是一个质数 m^k=(m^a)^b=（m^b)^a k=a*b;那么明显有重复的数据 所以k只能选质数
但当k为质数还有一种情况 比如x^3=y^5的情况 x=t^5 y=t^3;所以也会重复
根据题意的数据范围 我们可以k（质数）最大为61
还有就是 我们求m^k 求得不就是n^(1/t) 我们可以选择pow(n,1/t);只要能开出来，那么前面的也一定存在

比如你9开2次方等于3 不就证明存在三之前2个数，在这里我们先不管1这个数 因为重复 我们最后单独加
质数表 prime[17]={2,3,5,7,11,13,17,19,23,29,31,37,43,47,53,59,61}
因此我们可以选择容斥原理
我们假设 A[i] 表示i个素数出现（i<=3,2*3*5*7>61 够了）
结果等于 A[1]-A[2]+A[3]（感觉描述的有问题，但意思大概这样）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<vector>
#include<cstdlib>
#include<string>
#define eps 0.000000001
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
ll n;
int prime[18]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll get(int x){
    return pow(n,1.0/x)-1;//减1是为了去掉1
}
int main(){
    while(scanf("%lld",&n)!=EOF){
        ll sum1=0;
        ll sum2=0;
        ll sum3=0;
        for(int i=0;i<17;i++)sum1=sum1+get(prime[i]);
        for(int i=0;i<17;i++)
        for(int j=i+1;j<17;j++)sum2=sum2+get(prime[i]*prime[j]);
        for(int i=0;i<17;i++)
        for(int j=i+1;j<17;j++)
        for(int k=j+1;k<17;k++)
        sum3=sum3+get(prime[i]*prime[k]*prime[j]);
        cout<<sum1-sum2+sum3+1<<endl;
    }
}

Author

Eddy