Eddy's愛好

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2901????Accepted Submission(s): 1416

?

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

大概題意是要你輸出1到n中，能夠表示成a^b的數，a,b都是大于0的整數的個數，
其中b大于1。
因為1到n中，能夠完全開平方的個數就是（n^0.5）的整數部分，以此類推可以得到，完全開立方，完全開四次方各種的次數。這樣的話，要枚舉的數量太大，有什么辦法可以讓枚舉的數量減少呢？有的，由于任意一個大于1的整數都可以表示成兩個素的乘積，于是，能夠完全開平方的個數包括了能夠完全開四次方，八次方，十六次方以此類推的個數。于是，可以知道，只需要枚舉能夠完全開素數次方的個數即可。又因為n最大不會超過10^18，由于64位整型號能夠表示的最大數大概就是9*10^18多，所以不需要特地寫個大數。又因為這樣，所以素數只需要枚舉到大小不超過63即可，因為2^63-1就是64位整型的最大值，所以這個n最大，開個63次方的整數部分結果肯定為1，為1的話就代表能夠1到n中能夠完全開這個次方的數只有1個，又因為1能夠開任意次方，所以，這個數肯定是1啦，于是超過63的素數沒必要枚舉了，因為只有1能夠開這么多次方。對于一個數n，從小到大枚舉到使n開次方為1即可，再把前面所有開次方的結果都累加，再除去之中重復的部分，最終結果就是題意所要求的個數。

重復的部分是說，能夠完全開六次方的肯定也能夠完全開二次方和三次方，這個能完全開六次方的個數被重復加了一次，所以要減去一次，以此類推把所有重復的部分除去即可。

還有一點，這個題目，有的人用long long讀入n的時候，會wa，這個的話，是各種編譯器的原因，用cin讀入就好了，至于有的人說缺失精度什么的，只是想多了。

#include<iostream> #include<cmath> using namespace std; int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}; void result(long long x) {int i,j,k;long long tmp,ans=1;for(i=0;;i++){tmp=(long long)(pow(x,1.0/prime[i]));if(tmp<2)break;ans+=tmp-1;for(j=i+1;;j++){tmp=(long long)(pow(x,1.0/(prime[i]*prime[j])));if(tmp<2)break;ans-=tmp-1;for(k=j+1;;k++){tmp=(long long)(pow(x,1.0/(prime[i]*prime[j]*prime[k])));if(tmp<2)break;ans+=tmp-1;}}}printf("%lld\n",ans); } int main() {long long x;while(cin>>x)result(x); }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu-2204（容斥原理）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。