学步园

       不错的思考题，可找规律。人生第一次真正意义上的写证明。题意：如果一个数是两个不同的数的幂，那么这个数就称之为超级幂，比如64 = 8^2 = 4^3。因此64是一个超级幂。没有输入，请输出0到2^64-1范围内的所有超级幂。

       我的解题思路：首先要找出超级幂的规律，根据样例明显会看出来超级幂不能算本身的1次幂，我们试着把数都分解成幂形式来看（1特殊）。

16 = 2^4 = 4^2

64 = 2^6 = 4^3 = 8^2

81 = 3^4 = 9^2

256 = 2^8 = 4^4 = 16^2

512 = 2^9 = 8^3

......

看看能找到什么规律？看一下每个数分解成幂形式的指数部分，4的因数有2，6的因数有2和3，8的因数有2和4，等等。好像是在分解质因数，那么我们可以猜出超级幂分解成指数最大的幂形式时，这个指数是一个合数。大胆假设：如果一个数可以表示成某个数的合数次幂，那么这个数是超级幂，否则不是（1特殊）。

实际上我们可以这样证明：

设X = A^a（X，A，a都是整数，a 是合数，A不为1）。

因为a是合数，所以a必能分解成两个不是a和1的数的乘积，暂且表示为a = b × c（b和c可能相等，但是不会等于1或者a本身）。

因此X = A^a = A^(b×c) = (A^b)^c，如果说我们把A^b表示成B的话，那么现在X就能够被表示成超级幂了

X = A^a = B^c 。

充分性证毕。再证必要性：

设超级幂X = A^a = B^b = C^c = ……（X，A，B，……，a，b，……都是整数，a，b，c，……等都是素数）

超级幂X至少可以表示成两种幂形式，A^a和B^b（a和b都是素数）。

那么可知A^a = B^b，可以化为A = B^(b/a)

因为a和b都是素数，所以b / a的值必定不会是整数，也就是说a不能整除b，所以嘛，呵呵，B^(b/a)就不会是整数，这与之前的条件冲突，所以嘛，超级幂必定可以表示成某个数的合数次幂。

必要性证毕。

证明完毕之后我们只需要把所有不大于2^64-1的合数次幂按顺序输出就行了。2^64-1的范围是无符号64位整型的范围，关于求幂，底数我们只需要枚举到2的16次方就行了，关于幂的合数我们只要把64范围内的数筛素数就行了。为了避免溢出，需要用到一些技巧，详情请见代码。

       我的解题代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <climits>
#include <algorithm>
#include <set>

using namespace std;

typedef unsigned long long ULong;
typedef long long Long;

const int N = 70;

bool isprime[N];
int primes[N], pn;
set<ULong> numset;

void InitRead();

void DataProcess();

void FastSieve(int maxn);

ULong FastPow(ULong base, ULong n);

int main()
{
    InitRead();
    DataProcess();
    return 0;
}

void InitRead()
{
    numset.clear();
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    pn = 0;
    FastSieve(N - 1);
    int cnt = 1 << 16;          //底数枚举的最大值，因为最小的合数是4
    for (int i=2; i<cnt; ++i)
    {
        int temp = ceil(64 / (log(i) / log(2)));    //这个值是刚好会溢出无符号64位整型范围的指数
        for (int j=4; j<temp; ++j)
        {
            if (isprime[j]) continue;
            numset.insert(FastPow(i, j));
        }
    }
    return;
}

void DataProcess()
{
    set<ULong>::iterator si;
    puts("1");
    for (si=numset.begin(); si!=numset.end(); ++si)
    {
        printf("%llu\n", *si);
    }
    return;
}

void FastSieve(int maxn)
{
    for (int i=2; i<=maxn; ++i)
    {
        if (isprime[i]) primes[pn++] = i;
        for (int j=0; j<pn; ++j)
        {
            if (i * primes[j] > maxn) break;
            isprime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;
        }
    }
    return;
}

ULong FastPow(ULong base, ULong n)
{
    ULong ans = 1;
    while (n != 0)
    {
        if (n & 1) ans *= base;
        base *= base;
        n >>= 1;
    }
    return ans;
}