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

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

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

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

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

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

可以枚舉了？

還是要注意容斥！

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

最多是幾層？

2*3*5=30

2*3*5*7=210已經大于60了，所以最多枚舉三重循環就好

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

只需要這一行代碼：

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

轉自：點擊打開鏈接

代碼：

#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 喜歡收集蝴蝶標本和郵票，但是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
10361000000000000000000 Sample Output
491001003332