uva 11752 -The Super Powers (数论)

港控/mmm° 2022-08-09 12:55 244阅读 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**

**1**

**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;
    }