Recently, Joey has special interest in the positive numbers that could be represented as M ^ N (M to the power N), where M and N are both positive integers greater than or equal to 2. For example, 4, 8, 9 and 16 are first four such numbers, as 4 = 2 ^ 2, 8 = 2 ^ 3, 9 = 3 ^ 2, 16 = 2 ^ 4. You are planning to give Joey a surprise by giving him all such numbers less than 2 ^ 31 (2147483648). List them in ascending order, one per line.
Sample Output
4 8 9 16 25 27 32 | | <-- a lot more numbers | 1024 1089 1156 1225 1296 1331 | | |
Author: SHEN, Guanghao
Source: Zhejiang University Local Contest 2008
SOURCE CODE :
#include<iostream>
#include<map>
using namespace std;
int main()
{
map<int, int> ma;
for(int M = 2; M <= 46340;M++)
{
long long int pow = M;
if(ma.find(M) != ma.end()) continue;
for(int N = 1; N < 32; N++)
{
pow *= M;
if(pow >= 2147483648) break;
ma[pow] = pow;
}
}
for(map<int,int>::iterator it = ma.begin();it != ma.end(); it++)
{
cout<<it->first<<endl;
}
return 0;
}
在第二层for循环的时候，我曾想过先算出最大的可能循环数，然后在进行循环，这样就省去了
的判断，但是怎么样才能判断最大循环次数呢？我用了log(numeric_limits<int>::max() * 1.0)/log(M*1.0)来计算，本来我还以为这样计算是最大的节省了时间，但是我错了，cmath的log方法，算法肯定不简单，因为我发现，就算我完成所有的计算，这个循环次数的耗时，占了总耗时的差不多20%左右的时间开销。看来，有时候还是不要自作聪明的好。
if(pow >= 2147483648) break;