HDU - 2204 Eddy’s愛好

題意：

給你一個正整數N，確定在1到N之間有多少個可以表示成M^K（K>1)的數

題解：

參考題解：
我們先舉例找找規律
1~10以內2的次方有多少個？有1²=1,2²=4,3²=9,一共三個，10開方(向下取整)為3
也就是1~n之間k次方數有多少個 ，等于n^(1/k)，這算是個結論其實
如果我們直接按這個計算，會發現有很多重復，比如有個數是2的次方，也有可能是4的次方，也有可能是6的次方，但是這些其實在2的次方中就已經計算了，而4，8是2的倍數，所以我們只需要管素數次方就行了，一個2就涵蓋了所有4，6，8等等。你也可以這么理解：如果M^(ab)也可以寫成(M^a)b，如果指數不是質數，那么一定可以每另外一組數字表示，且這組數字的指數是質數。所以說我們只需要統計指數是質數的數字能夠組成多少個n以內的數字。
那是不是這樣就沒有重復了？也不是，不同數之間有可能也有，就比如一個數是6的次方，他就被素數2次方和素數3次方同時給統計了，這個要用到容斥，比如27²和9³會重復是因為他們都能湊出指數6，所以我們需要減去指數6所得到的個數
舉個例子：
n=729
指數為2：2²,3²,4²,5²,6²…27²
指數為3：2³,3³,4³,5³,6³…9³
8²=2⁶和4³=2⁶就是重復的，我們用n計算出指數為6的個數，729^(1/6)=1,那么答案就是先+指數為2的，再+指數為3的，最后減指數為6的，這是容斥為2的情況
如果重復的是2，3，5的共同倍數30，同理+2+3+5- 2 * 3 -3 * 5 - 2 * 5 + 2 * 3 * 5(結合下圖應該能明白)，這是容斥的層數為3的情況

那容斥為4的情況呢？題目說了n在1e18的范圍內，說明m^k,k取值要小于61，而2 * 3 * 5<61<2 * 3 * 5 * 7，所以容斥四層的情況不用考慮，

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61}; int main() {ll n;while(cin>>n){ll ans=1;ll tmp;for(int i=0;;i++){tmp=(ll)pow(n,1.0/p[i]);if(tmp<2)break;//說明n開p[i]次方不足 ans+=tmp-1;for(int j=i+1;;j++){tmp=(ll)pow(n,1.0/p[i]/p[j]);if(tmp<2)break;ans-=tmp-1;for(int k=j+1;;k++){tmp=(ll)pow(n,1.0/p[i]/p[j]/p[k]);if(tmp<2)break;ans+=tmp-1;} } }cout<<ans<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的HDU - 2204 Eddy‘s爱好（尚未完全解决）的全部內容，希望文章能夠幫你解決所遇到的問題。

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