UVA11752 The Super Powers-蒲公英云

UVA11752 The Super Powers

最近几天的状态着实不好，数电设计的答辩不能更逗，万幸是终于到家了，看到群里有各种群赛十分开心，希望能找回刷题的动力，调整下状态。

这道题是很久前做的，细节记不太清了。。。

数据范围1到 2^64 -1，可以看出需要用 unsigned long long ，其中1单独考虑，仔细分析可知满足条件的数必然是一个数的合数次方，最小是4，一个数的4次方在2^64 -1之内，那最大只能到65535。暴力枚举然后去除重复的就行了。可以用limit=ceil( 64/(log(i)/log(2)) )-1来判断一个数乘方数的上界。

去重我用的是STL的set，用数组排序再用unique函数也行。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define i64u unsigned long long
int heshu[50]={4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28
            ,30,32,33,34,35,36,38,39,40,42,44,45,46,48,49,50,51,52,54,55,56,57,58,60,62,63,64};
i64u POW (i64u s,i64u index)
{
    i64u ans=1;
    while (index>=1)
    {
        if ((index&1)==1)   //奇数
            ans=(ans*s);
        index>>=1;
        s=s*s;
    }
    return ans;
}
set<i64u> s;
int main ()
{
    int id=0,i;
    printf("1\n");
    for (i=2;i<65536;i++)
    {
        int limit;
        if (i==2) limit=63;
        else limit=ceil( 64/(log(i)/log(2)) )-1;
        if (limit <4) break;
        for (int j=0;heshu[j]<=limit;j++)
            s.insert(POW(i,heshu[j]) );
    }
    set<i64u>::iterator it;
    for (it=s.begin();it!=s.end();it++)
        printf("%llu\n",*it);
    return 0;
}