hdoj 2204 Eddy's爱好

原文链接：http://www.cnblogs.com/DrunBee/archive/2012/09/05/2672546.html

题意：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。

我们可以由n^(1/p)，知道指数为p的有多少个数。

通过观察，可以发现若一个数可以表示成x^(k*t)，则可以表示成(x^k)^t。因此指数必然为素数。

枚举素数便可以得到指数为p的个数，但是可能出现重复，例如：x^3=y^5，其中x=t^5，y=t^3。

运用容斥原理，设a[i]表示指数为第i个素数的个数，那么答案等于满足一个的，减去两个的，加上三个的……

由于2^60>10^18，2*3*5*7>60，所以只要枚举到三即可。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#define EPS 1e-8

#define MAXN 65

typedef long long LL;

using namespace std;

bool p[MAXN];

vector<int> prime;

void Init()

{

    int i, j;

    memset(p, true, sizeof(p));

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

    {

        if (p[i])

        {

            for (j = i * i; j < MAXN; j += i)

                p[j] = false;

        }

    }

    prime.clear();

    for (i = ; i < MAXN; i++)

    {

        if (p[i])

            prime.push_back(i);

    }

}

int main()

{

    LL n, tmp;

    int i, j, k, ans;

    Init();

    while (~scanf("%I64d", &n))

    {

        ans = ;

        for (i = ; i < (int) prime.size(); i++)

        {

            tmp = (LL) (pow((double) n, 1.0 / prime[i]) + EPS);

            if (tmp == )

                break;

            ans += tmp - ;

        }

        for (i = ; i < (int) prime.size(); i++)

        {

            for (j = i + ; j < (int) prime.size(); j++)

            {

                tmp = (LL) (pow((double) n, 1.0 / (prime[i] * prime[j])) + EPS);

                if (tmp == )

                    break;

                ans -= tmp - ;

            }

        }

        for (i = ; i < (int) prime.size(); i++)

        {

            for (j = i + ; j < (int) prime.size(); j++)

            {

                for (k = j + ; k < (int) prime.size(); k++)

                {

                    tmp = (LL) (pow((double) n,

                                    1.0 / (prime[i] * prime[j] * prime[k])) + EPS);

                    if (tmp == )

                        break;

                    ans += tmp - ;

                }

            }

        }

        printf("%d\n", ans);

    }

    return ;

}

巴特西

hdoj 2204 Eddy's爱好

最新文章

热门文章