uva 11752 - The Super Powers(数论+枚举技能)

uva 11752 - The Super Powers(数论+枚举技巧)

题目链接：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 <stdio.h>
#include <string.h>
#include <math.h>
#include <set>
#include <algorithm>

using namespace std;
typedef unsigned long long ll;
const int N = 105;
int g, v[N], a[N];

void init () {
	g = 0;
	memset(v, 0, sizeof(v));

	for (int i = 2; i <= 64; i++) {
		if (v[i]) {
			a[g++] = i;
			continue;
		}

		for (int j = i * 2; j <= 64; j += i) v[j] = 1;
	}
}

void solve () {
	set<ll> ans;
	ans.insert(1);

	ll MaxT = 1<<16;
	for (ll i = 2; i < MaxT; i++) {
		int ti = ceil(64 * log(2) / log(i)) - 1;
		ll now = i * i * i * i;
		ans.insert(now);
		for (int j = 1; a[j] <= ti; j++) {
			now *= (a[j] - a[j-1] == 1 ? i : i * i);
			ans.insert (now);
		}
	}

	for (set<ll>::iterator i = ans.begin(); i != ans.end(); i++)
		printf("%llu\n", *i);
}

int main () {
	init();
	solve ();
	return 0;
}