uva 11752 The Super Powers 素数+大数判断大小

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2852

题意：找到在[1,2^64-1]区间范围内的所有Super Powers数，Super Powers数指的是可以写成另外两个正数的次幂；

例如：1=1^1,1=1^20; 64=8^2,64=4^4;

思路：1另外算，从2开始，他的指数如果不是素数，由于算数基本定理，即可将指数分解成另外多个素数的乘积，即是Super Powers数；

利用log判断是否超过2^64-1,记得用无符号long long ；

#include<bits/stdc++.h>

using namespace std;

#define ll unsigned long long

#define esp 1e-13

const int N=1e3+,M=1e6+,inf=1e9+,mod=;

const int MAXN=;

ll prime[MAXN];

bool vis[MAXN];

map<ll,ll>flag;

struct cmp1{

    bool operator ()(ll &a,ll &b){

        return a>b;

    }

};

priority_queue<ll, vector<ll> ,cmp1>q;

ll Prime(ll n)

{

    ll cnt=;

    memset(vis,,sizeof(vis));

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

    {

        if(!vis[i])

        prime[cnt++]=i;

        for(int j=;j<cnt&&i*prime[j]<n;j++)

        {

            vis[i*prime[j]]=;

            if(i%prime[j]==)

            break;

        }

    }

    return cnt;

}

ll quickpow(ll a,ll b)

{

    ll sum=;

    while(b)

    {

        if(b&)sum*=a;

        a*=a;

        b>>=;

    }

    return sum;

}

int main()

{

    ll cnt=Prime(MAXN);

    ll x,y,z,i,t;

    ll ans=;

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

    ans+=quickpow(2ll,i);

    printf("1\n");

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

    {

        ll sum=i,t=;

        double hh=(double)(log(sum*1.0)/log())+(double)(log(i*1.0)/log())-(double)(log(ans*1.0)/log());

        while(hh<=-esp)

        {

            sum*=i;

            t++;

            if(!flag[sum]&&vis[t])

            {

                q.push(sum);

                flag[sum]=;

            }

            hh=(double)(log(sum*1.0)/log())+(double)(log(i*1.0)/log())-(double)(log(ans*1.0)/log());

        }

    }

    while(!q.empty())

    {

        printf("%llu\n",q.top());

        q.pop();

    }

    return ;

}