UVA11752 The Super Powers —— 数论、枚举技巧

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

题意：

一个超级数是能够至少能表示为两个数的幂，求1~2^64-1内的超级数。

题解：

1.可知对于 n = a^b，如果b是合数，那么n同样可以表示为： n = (a^k)^c，其中k*c = b。所以只需要枚举底数，然后再枚举指数，如果指数为合数，那么它就是一个超级数。

2.由于2^64-1已经是 unsigned LL 的最大值了，为了避免溢出，指数应该从当前底数能达到的最大指数开始枚举。

3.由于一个超级数可能被多次访问到，所以用STL的 set 可以解决重复、离散化的问题，而且还能排序。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

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

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = 1e5+;

 int vis[];

 void init()

 {

     int m = sqrt(+0.5);

     for(int i = ; i<=m; i++) if(!vis[i]) {

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

             vis[j] = ;

     }

 }

 typedef unsigned long long ull;

 set<ull>s;  //用set完成了排序加去重的功能

 int main()

 {

     init(); //标记在64以为的合数

     for(ull i = ;; i++)    //枚举底数

     {

         int t = ceil(*log()/log(i)) - ;

         if(t<) break;

         ull x = ;

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

         {

             x *= i;

             if(vis[j]) s.insert(x);

         }

     }

     s.insert();

     set<ull>::iterator it;

     for(it = s.begin(); it!=s.end(); it++)

         cout<<*it<<endl;

 }

巴特西

UVA11752 The Super Powers —— 数论、枚举技巧

最新文章

热门文章