uva 11752 -The Super Powers (数论)-蒲公英云

uva 11752 -The Super Powers (数论)

港控/mmm° 2022-08-09 12:55 241阅读 0赞

We all know the Super Powers of this world and how they manage to get advantages in political warfareor even in other sectors. But this is not a political platform and so we will talk about a different kindof super powers — “The Super Power Numbers”. A positive number is said to be super power when itis the power of at least two different positive integers. For example 64 is a super power as 64 = 82 and64 = 43. You have to write a program that lists all super powers within 1 and 264 ? 1 (inclusive)

Input
This program has no input.

Output

Print all the Super Power Numbers within 1 and 2^64 -1. Each line contains a single super power number and the numbers are printed in ascending order.

Sample Input

No input for this problem

Partial Judge Output

16
64

81
256

512
.
.
.

题目大意：超级幂（要求要打到1-2^64 -1的数，该数是两个或以上的正整数的幂次方），没有输入，只有输出打表！

思路：首先想到了素数的合数次方，最小的合数（也就是幂）是4，那么最大的底数（也就是要打的素数表的最大值是2^16，也就是1<<16，开到65536的数组足够），按照这种思路，却T了很多次，最后问学长，才知道打的时候没有判断，到最后打的太多反而T了，加判断的方法是判断指数要小于ceil(64.0/log(i)*log(2))，按说到此应该Ac了，可是又wa了一次，原来一开始推错了，应该打所有数的合数次方，最后去重即可，表示用vector打素数的合数次方打的好伤心，正解用set/map存，去重和排序一体。

code：

# include<iostream>
# include<cstdio>
# include<cstring>
# include<set>
# include<cmath>
# include<algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=65546;
set<ull>s;
set<ull>::iterator it;
bool vis[N];
ull mi (int n,int m)    //二分幂
{
    if (m==0) return 1;
    if (m%2==0)
        return mi(n,m/2)*mi(n,m/2);
    else
        return n*mi(n,m/2)*mi(n,m/2);
}
void get_prim()    //打素数表
{
    int i,j;
    memset(vis,true,sizeof(vis));
    vis[0]=vis[1]=false;
    for(i=2;i<N;++i)
    {
        if(!vis[i])  continue;
        for(j=i+i;j<N;j+=i)
            vis[j]=false;
    }
}
int main()
{
    int i,j;
    s.insert(1);
    get_prim();
    for(i=2;i<=65536-1;++i)
    {
        double t=ceil(64.0/log(i)*log(2))-1;  //关键：加指数判断
        for(j=4;j<=t;++j)
        {
            if(vis[j]) continue;
                s.insert(mi(i,j));
        }
    }
    for(it=s.begin();it!=s.end();++it)
      printf("%llu\n",*it);
    return 0;
}