UVA 11752 The Super Powers

题目链接:点我

题目

---

题意:

输出所有的可以表示为至少两个不同数的次方的形式数.

思路:

先用素数筛选法找出64以内的合数，以为只有幂是合数才可以进行拆分。然后枚举底数进行判断，所有小于2^{64-1的数都是满足的，这里有一个技巧，就是说2}64-1已经是unsign long long 的最大值了，那么超过它的数就会变成负数。但其实i的最大次幂是可以求的，x = logi(2^64-1) = log(2^64-1) / log(i);

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
using namespace std;

int ex[100]={ 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};
typedef unsigned long long ull;

int main(){
    set<ull> q;
    q.insert(1);
    ull maxn=( 1 << 16) - 1;
    for(ull i = 2; i <= maxn; ++i){
        ull tmp = i * i * i * i;//底数
        q.insert(tmp);
        int k = ceil(64 * log(2)/log(i)) - 1;//指数的上限
        for(int j = 1; ex[j] <= k; ++j){
            if(ex[j] ==ex[j-1] + 1)
                tmp *= i;
            else tmp =  tmp * i * i;
           q.insert(tmp);
        }
    }
    for(set<ull>::iterator it = q.begin();it != q.end();++it)
        cout<<*it<<endl;
    return 0;
}