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个多小时啊。。。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 using namespace std;10 const double EPS=1e-8;11 #define mem(x,y) memset(x,y,sizeof(x))12 const int INF=0x3f3f3f3f;13 vector
             
              p;14 typedef long long LL;15 const LL MAXN=1e18;16 LL N,sum,I;17 void getprim(){18 int pp[110];19 mem(pp,0);20 for(int i=2;i<=60;i++){21 for(int j=i*i;j<=60;j+=i)22 pp[j]=1;23 }24 for(int i=2;i<=60;i++)if(!pp[i])p.push_back(i);25 //for(int i=0;i
              
               N)tep--;31 tep--;32 if(tep>0)sum+=tep*((I&1)?1:-1);//少了括号。。。。。。。。 33 return;34 }35 if(pos>=17)return;36 if(cur*p[pos]<=60)rc(cur*p[pos],pos+1,k-1);37 rc(cur,pos+1,k);38 }39 int main(){getprim();40 while(~scanf("%I64d",&N)){41 sum=0;42 for(I=1;I<=3;I++){43 rc(1,0,I);44 }45 printf("%I64d\n",sum+1);46 }47 return 0;48 }

转载地址：http://fxgrl.baihongyu.com/

你可能感兴趣的文章