/** 题目：The Super Powers UVA 11752 链接：https://vjudge.net/contest/154246#problem/Y 题意：求无符号长整形以内的数满足至少可以用两种不同的次方来表示。比如64 = 2^6 = 8^2； 一个数的1次方不算数。 思路： 分析过程如下： 1 = 1^1 1^2 1^3 16 = 2^4 4^2 64 = 2^6 8^2 81 = 3^4 9^2 256 = 2^8 16^2 512 = 2^9 8^3 设Max为最大的可能获得的值。 Max = a^e1 or a^e2 or ... (2<=e1<e2) a <= Max开三次方根=[1,1e7] 前面我猜想一个满足条件的数是某一个素因子的合数次方。 (2*3)^4 = (4*9)^2 含有多个素数。实际上不止一个素因子。 那么底数在（Max开三次方根）内是任意可能的。 有一点可以肯定：一个数的合数次方一定是满足条件的数。 底数在[1,1e7]以内。然后合数范围在64以内。然后set存数并去重；时间复杂度过大。 避免使用set？尝试提前去重。 2^4, 2^6, 2^8, 2^9, 2^10, 2^12, 2^14, 2^15. 取2^8 = 4^4 重复了。 2^12 = 4^6 = 8^4 （保证幂是合数） 重复了。 而：2^4, 2^6, 2^9, 2^10, 2^14, 2^15不会再重复。因为幂都是两个素数相乘的结果。 如何通过现在的某些计算来预测将来的某些数不用再重复计算？ 或者通过一些计算来判定当前的数已经算过了。 4^4， 4^6， 4^8， 4^9， 4^10， 4^12. 好像这些都是重复了的。那么。。。所有的底数为合数都会被重复。 只要计算底数为素数的就行了？ (2*3)^4 = (4*9)^2 含有多个素数。从哪里得来？ 再试试其他合数为底数的情况。 6^4, 6^6, 6^5, 6^8, 6^9, 6^10. 6^4没有重复过。并不是所有的底数为合数都会被重复。 2^12 = 8^4 可以得知如果以前出现过。那么底数应该可以开根号才行，即底数可以表示成一个数的次方，次方>1。 新结论：底数如果是某个数的次方，那么它的所有合数幂都重复过。其他情况均没有重复过。 问题好像重复了。都是某个数的次方。只不过题目为至少两个。 那么对每一个非次方数的底数a。它的贡献为a^e. (e为合数，且a^e<=2^64 - 1) 还是往这方面处理：如何通过现在的某些计算来预测将来的某些数不用再重复计算？ 预处理64以内的合数的约数对，即：两个约数相乘等于本身为一对。这样通过约束对来判断是否那些底数会重复。 当两个约数至少一个>=4的合数时候，比如d1,d2；那么(x^d1)^d2 or (x^d2)^d1 都要去重。 解题方法： 预处理64以内的约数。以及每一个约数的约数对。 枚举底数a在[1,1e7]内。 对每一个底数a枚举它约数次方。并如果次方可以分解成两个约数，其中一个是>=4的约数。那么底数^另一个约数形成的数不能再作为计算的底数。 猜想：如果时间超限，适当降低[1,1e7]右边界的范围。 为了避免底数的合数次方超出unsigned long long 范围，所以用log对数来处理。 其实应该可以很快想到的，但是走了很多弯路。积累经验。多思考。 */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<vector> #include <cmath> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e5+10; const double eps = 1e-6; vector<int> v[64];//存储约数对。 int isHe[64];//isHe[i] == 1表示这是一个合数。 int he[64], z;//存储合数。 ull ans[100010], cnt;//注意这里不能和maxn一直相同。因为ans数量可能更多。 //经测试最多67385个； int flag[maxn]; ll f(ll a,ll b) { ll p = 1; while(b){ if(b&1) p*=a; a = a*a; b >>= 1; } return p; } void init() { memset(isHe, 0, sizeof isHe); for(int i = 2; i < 64; i++){ if(isHe[i]==0){ for(int j = i*i; j < 64; j+=i){ isHe[j] = 1; } } } z = 0; for(int i = 2; i < 64; i++){ if(isHe[i]){ he[z++] = i; for(int j = 2; j*j < 64; j++){ if(i%j==0){ if(he[j]||he[i/j]){ v[i].push_back(j); v[i].push_back(i/j); } } } } } ull mas = (1<<64)-1; //cout<<"mas = "<<mas<<endl; cnt = 0; for(int i = 2; i < maxn; i++){ if(flag[i]) continue; ull p = i, num = 1; for(int j = 0; j < z; j++){ if(he[j]>log(mas)/log(i)-eps) break;///不加eps，会存在误差，比如2^64次方可能会算进去。然后p = 0; while(num<he[j]){ num++; p *= i; } if(num<he[j]) break; ans[cnt++] = p; int len = v[he[j]].size(); for(int k = 0; k < len; k+=2){ if(isHe[v[he[j]][k]]){ ull temp = f(i,v[he[j]][k+1]); if(temp>=maxn) continue; flag[temp] = 1; } if(isHe[v[he[j]][k+1]]){ ull temp = f(i,v[he[j]][k]); if(temp>=maxn) continue; flag[temp] = 1; } } } } sort(ans,ans+cnt); printf("1 "); for(int i = 0; i < cnt; i++){ printf("%llu ",ans[i]); } } int main() { init(); return 0; }