http://acm.hdu.edu.cn/showPRoblem.php?pid=2204

給定n，求1-n中有多少個可以表示成M的K次方的數(shù)。K>1

題意很簡單，但是怎么想？題面上說到了素數(shù)，第一想法就是K從素數(shù)開始枚舉！

當(dāng)K不是素數(shù)時，必然是重復(fù)算過的！比如K=6時，一定會有一個（M1的2次方）的3次方=（M2的3次方）的2次方

那么，最大素數(shù)是多少？n最大值是1e18，所以呢，找到一個x，使得2的x次方大于n的最大值，x=60

所以取61為最大素數(shù)肯定滿足條件了

可以枚舉了？

還是要注意容斥！

例如15=3*5，所以，3的要加，5的要加，15的要減

最多是幾層？

2*3*5=30

2*3*5*7=210已經(jīng)大于60了，所以最多枚舉三重循環(huán)就好

現(xiàn)在是有了n和K，怎么得到M呢？

只需要這一行代碼：

所以，注意：一開始ans賦初始化就為1，之后，所有的計算把1除掉就好

轉(zhuǎn)自：點擊打開鏈接

代碼：

#include<iostream>#include<cmath>#include<cstdio>using namespace std;typedef long long ll;const double eps = 1e-9;int prime[18] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};ll ans, n;void dfs(int cur, int ex, int pos){    if(pos > 3) return ;    for(int i = cur; i < 18; i++)    {        ll num = pow(n, 1.0/(ex*prime[i]))+eps;        num--;        if(num > 0)            ans += num*(pos%2 ? 1 : -1);        dfs(i+1, ex*prime[i], pos+1);    }}int main(void){    while(cin >> n)    {        ans = 0;        dfs(0, 1, 1);        printf("%lld/n", ans+1);    }    return 0;}
Eddy's愛好
Time Limit: 3000/1000 MS (java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2433    Accepted Submission(s): 1116Problem DescriptionIgnatius 喜歡收集蝴蝶標(biāo)本和郵票，但是Eddy的愛好很特別，他對數(shù)字比較感興趣，他曾經(jīng)一度沉迷于素數(shù)，而現(xiàn)在他對于一些新的特殊數(shù)比較有興趣。這些特殊數(shù)是這樣的：這些數(shù)都能表示成M^K，M和K是正整數(shù)且K>1。正當(dāng)他再度沉迷的時候，他發(fā)現(xiàn)不知道什么時候才能知道這樣的數(shù)字的數(shù)量，因此他又求助于你這位聰明的程序員，請你幫他用程序解決這個問題。為了簡化，問題是這樣的：給你一個正整數(shù)N，確定在1到N之間有多少個可以表示成M^K（K>1)的數(shù)。 Input本題有多組測試數(shù)據(jù)，每組包含一個整數(shù)N，1<=N<=1000000000000000000(10^18). Output對于每組輸入，請輸出在在1到N之間形式如M^K的數(shù)的總數(shù)。每組輸出占一行。 Sample Input
10361000000000000000000 Sample Output
491001003332