HDU 2204 Eddy's爱好（容斥原理dfs写法）题解

题意：定义如果一个数能表示为M^k，那么这个数是好数，问你1~n有几个好数。

思路：如果k是合数，显然会有重复，比如a^(b*c) == (a^b)^c，那么我们打个素数表，指数只枚举素数，2^60 > 1e18，所以打60以内素数就够了。但是显然指数为素数依然会有重复的，比如（a^b）^c == (a^c)^b，这里就要用到容斥了。我们如果用一个数组a[i]表示指数为第i个素数的数的个数，那么最终答案应该是，加上一个的，减去两个的，加上三个的（因为2 * 3 * 5 * 7 > 60，最多只能有三个相乘形成指数）。如果我要算出指数为p的这样的数有几个，那么可以计算pow(n,1.0/p)。先写了一个朴素版的，纯枚举；后来又写了一个dfs的，这样大于3也能用了。

讲一些小细节，每次算出个数我们都减去1这里是去掉了1^p，我们在最后答案加上1。最后一个样例答案是“1001003332”，我的“1001003331”但是过了。

容斥：对于几个集合求解并集大小，那么采用一种方法：加上所有单个集合，减去所有两个集合相并部分，加上所有三个集合相并部分，减去所有四个集合相并部分.....

参考：学习容斥原理

代码：

/*朴素写法1*/
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 20000 + 10;
const int seed = 131;
const int MOD = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
int prime[70], p[70], pn;
ll ans, n;
void get(){
    memset(p, 0, sizeof(p));
    pn = 0;
    for(int i = 2; i <= 60; i++){
        if(!p[i]){
            prime[pn++] = i;
            for(int j = i * i; j <= 60; j += i){
                p[j] = 1;
            }
        }
    }
}
int main(){
    get();
    while(~scanf("%lld", &n)){
        ans = 0;
        ll ret;
        for(int i = 0; i < pn; i++){
            ret = pow((double)n, 1.0 / prime[i]);
            if(ret == 1) break;
            ans += ret - 1;
        }
        for(int i = 0; i < pn; i++){
            for(int j = i + 1; j < pn; j++){
                ret = pow((double)n, 1.0 / (prime[i] * prime[j]));
                if(ret == 1) break;
                ans -= ret - 1;
            }
        }
        for(int i = 0; i < pn; i++){
            for(int j = i + 1; j < pn; j++){
                for(int k = j + 1; k < pn; k++){
                    ret = pow((double)n, 1.0 / (prime[i] * prime[j] * prime[k]));
                    if(ret == 1) break;
                    ans += ret - 1;
                }
            }
        }
        printf("%lld
", ans + 1);
    }
    return 0;
}

/*dfs写法*/
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 20000 + 10;
const int seed = 131;
const int MOD = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
int prime[60], p[70], pn;
ll ans, n, flag;
void get(){
    memset(p, 0, sizeof(p));
    pn = 0;
    for(int i = 2; i <= 60; i++){
        if(!p[i]){
            prime[pn++] = i;
            for(int j = i * i; j <= 60; j += i){
                p[j] = 1;
            }
        }
    }
}
void dfs(int start, int p, int times){
    if(times == 0){
        ll ret = pow((double)n, 1.0 / p);
        if(ret == 1) return;
        ret--;
        ans += flag * ret;
        return;
    }
    for(int i = start; i < pn; i++){
        dfs(i + 1, p * prime[i], times - 1);
    }
}
int main(){
    get();
    while(~scanf("%lld", &n)){
        ans = 0;
        ll ret;
        flag = -1;
        for(int i = 1; i <= 3; i++){
            flag *= -1;
            dfs(0, 1, i);
        }
        printf("%lld
", ans + 1);
    }
    return 0;
}