UVA 11752 The Super Powers（暴力）

时间：2023-03-10 08:02:27
UVA 11752 The Super Powers（暴力）

题目：https://cn.vjudge.net/problem/UVA-11752

题解：这里只讨论处理越界的问题。

　　　因为题目最上界是 264-1。 我们又是求次幂的。

　　　所以当我们就可以知道 i 的时候的界限 limit = 264-1 / i。如果刚好前一个次幂是 limit，那么再乘一个 i 刚好等于 264-1，按照题意是符合的。

　　　那么如果当前的 次幂 a 是大于 limit 的话，a*i 就一定越界（可以自己想一想为什么），这个时候就可以break了。

　　这一题用set 保存，因为set中不会出现重复元素，而且元素是从小到大的顺序排列的。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 #include <queue>

 #include <map>

 #include <stack>

 #include <set>

 using namespace std;

 typedef long long LL;

 typedef unsigned long long uLL;

 #define ms(a, b) memset(a, b, sizeof(a))

 #define pb push_back

 #define mp make_pair

 const LL INF = 0x7fffffff;

 const int inf = 0x3f3f3f3f;

 const int mod = 1e9+;

 const int maxn = +;

 const int maxm = +;

 bool heshu[maxn];

 set<uLL> ans;

 int main() {

 #ifdef LOCAL

     freopen("input.txt", "r", stdin);

 //        freopen("output.txt", "w", stdout);

 #endif

 //    ios::sync_with_stdio(0);

 //    cin.tie(0);

     ms(heshu, false);

     for(int i = ;*i<;i++){

         for(int j = ;i*j<;j++)

             heshu[i*j]=true;

     }

     uLL top = (<<)-1uLL;

     for(uLL i = 2uLL;i<65536uLL;i++){

         uLL limit = top / i;

         uLL now = 1uLL*i*i*i*i;

         for(int j = ;j<;j++){

             if(heshu[j])

                ans.insert(now);

             if(now>limit)   break;

             now*=i;

         }

     }

     ans.insert(1uLL);

     set<uLL>::iterator q;

     for(q = ans.begin();q!=ans.end();q++)

         cout << *q << endl;

 //    cout << ans.size() << endl;

 }

相关文章