Eddy's爱好（dfs+容斥）

时间：2023-01-24 01:05:34

Eddy's爱好

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

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

题解：错了半天。。。。唉，前期各种试，刚开始少考虑了好多素数，，写的果断错，然后就是思路走歪了，竟然想到了多个2或3，自己乘自己的情况。。。最后借助了还是网上的做法。。。3个多小时啊。。。

代码：

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<set>

 #include<map>

 #include<vector>

 using namespace std;

 const double EPS=1e-;

 #define mem(x,y) memset(x,y,sizeof(x))

 const int INF=0x3f3f3f3f;

 vector<int>p;

 typedef long long LL;

 const LL MAXN=1e18;

 LL N,sum,I;

 void getprim(){

     int pp[];

     mem(pp,);

     for(int i=;i<=;i++){

         for(int j=i*i;j<=;j+=i)

         pp[j]=;

     }

     for(int i=;i<=;i++)if(!pp[i])p.push_back(i);

     //for(int i=0;i<p.size();i++)printf("%d ",p[i]);puts("");

 }

 void rc(int cur,int pos,int k){

     if(k==){

         LL tep=pow(N,1.0/cur);

         if(pow(tep,0.0+cur)>N)tep--;

         tep--;

         if(tep>)sum+=tep*((I&)?:-);//少了括号。。。。。。。。

         return;

     }

     if(pos>=)return;

     if(cur*p[pos]<=)rc(cur*p[pos],pos+,k-);

     rc(cur,pos+,k);

 }

 int main(){getprim();

     while(~scanf("%I64d",&N)){

         sum=;

         for(I=;I<=;I++){

             rc(,,I);

         }

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

     }

     return ;

 }

相关文章