UVA 11752 超級冪

Z -?The Super Powers Time Limit:1000MS?????Memory Limit:0KB?????64bit IO Format:%lld & %llu Submit?Status?Practice?UVA 11752

Description

題意：定義一個數為超級冪，當這個數能表示成至少兩個不同數字的冪時。如16=2^4，16=4^2。輸出1~2^64-1范圍內的超級冪。 思路：顯然一個數能稱為超級冪，這個數肯定是一個數的合數冪，即a^(b*c)=(a^b)^c=(a^c)^b。而最小合數是4，所以只需從1枚舉到2^16即可。現在重點再判溢出，2^64-1顯然剛好是ull的范圍，直接判x<=0||x>INF顯然是會出錯的，因為有可能一次溢出非常多又溢回正數了。這里方法是轉換為double取對數，double的范圍比要多，而且取對數還可以把指數放下來。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype>
#define ll long long
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define REPP(i,a,b,t) for(int (i)=(a);(i)<=(b);(i)+=(t))
#define PII pair<int,int>
#define MP make_pair
#define PB push_back
#define RI(x) scanf("%d",&(x))
#define RLL(x) scanf("%lld",&(x))
#define RI64(x) scanf("%I64d",&(x))
#define DRI(x) int x;scanf("%d",&(x))
#define DRLL(x) ll x;scanf("%lld",&(x))
#define DRI64(x) llx;scanf("%I64d",&(x))
#define MS0(a) memset((a),0,sizeof((a)))
#define MS1(a) memset((a),0,sizeof((a)))
#define MS(a,b) memset((a),(b),sizeof((a)))using namespace std;typedef unsigned long long ull;
const int maxn=1000100;
const ull INF=(1LL<<64)-1;
const double EPS=0.0000000001;
const double Pi=acos(-1.0);bool isprime[maxn];
vector<int> np;
set<ull> vis;ll qpow(ull n,ull k)
{ull res=1;while(k){if(k&1) res*=n;n*=n;k>>=1;}return res;
}void getNotPrime()
{MS(isprime,1);REP(i,2,maxn-1){if(!isprime[i]) continue;REPP(j,i*2,maxn-1,i) isprime[j]=0;}REP(i,2,64){if(!isprime[i]) np.PB(i);}
}int main()
{getNotPrime();puts("1");REP(i,2,(1<<16)){REP(j,0,(int)np.size()-1){if(np[j]*log10(i*1.0)>=64*log10(2.0)) break;ull x=qpow(i,np[j]);//cout<<i<<" "<<np[j]<<endl;getchar();if(vis.find(x)==vis.end()){vis.insert(x);}}}for(set<ull>::iterator it=vis.begin();it!=vis.end();it++) printf("%llu\n",*it);return 0;
}

View Code

?

轉載于:https://www.cnblogs.com/--560/p/4572803.html

總結

以上是生活随笔為你收集整理的UVA 11752 超级幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。