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 =  + ;

const int seed = ;

const int MOD =  + ;

const int INF = 0x3f3f3f3f;

int prime[], p[], pn;

ll ans, n;

void get(){

    memset(p, , sizeof(p));

    pn = ;

    for(int i = ; i <= ; i++){

        if(!p[i]){

            prime[pn++] = i;

            for(int j = i * i; j <= ; j += i){

                p[j] = ;

            }

        }

    }

}

int main(){

    get();

    while(~scanf("%lld", &n)){

        ans = ;

        ll ret;

        for(int i = ; i < pn; i++){

            ret = pow((double)n, 1.0 / prime[i]);

            if(ret == ) break;

            ans += ret - ;

        }

        for(int i = ; i < pn; i++){

            for(int j = i + ; j < pn; j++){

                ret = pow((double)n, 1.0 / (prime[i] * prime[j]));

                if(ret == ) break;

                ans -= ret - ;

            }

        }

        for(int i = ; i < pn; i++){

            for(int j = i + ; j < pn; j++){

                for(int k = j + ; k < pn; k++){

                    ret = pow((double)n, 1.0 / (prime[i] * prime[j] * prime[k]));

                    if(ret == ) break;

                    ans += ret - ;

                }

            }

        }

        printf("%lld\n", ans + );

    }

    return ;

}

/*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 =  + ;

const int seed = ;

const int MOD =  + ;

const int INF = 0x3f3f3f3f;

int prime[], p[], pn;

ll ans, n, flag;

void get(){

    memset(p, , sizeof(p));

    pn = ;

    for(int i = ; i <= ; i++){

        if(!p[i]){

            prime[pn++] = i;

            for(int j = i * i; j <= ; j += i){

                p[j] = ;

            }

        }

    }

}

void dfs(int start, int p, int times){

    if(times == ){

        ll ret = pow((double)n, 1.0 / p);

        if(ret == ) return;

        ret--;

        ans += flag * ret;

        return;

    }

    for(int i = start; i < pn; i++){

        dfs(i + , p * prime[i], times - );

    }

}

int main(){

    get();

    while(~scanf("%lld", &n)){

        ans = ;

        ll ret;

        flag = -;

        for(int i = ; i <= ; i++){

            flag *= -;

            dfs(, , i);

        }

        printf("%lld\n", ans + );

    }

    return ;

}

巴特西

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

最新文章

热门文章