杰拉斯的博客

幸运妈妈

Time Limit:1000MS Memory Limit:32768K

Description

某外星国并没实行计划生育，决定选出幸运妈妈。具体如下： 假设妈妈生了N个孩子，若N能表示成某个正整数X的K次幂（K＞1），N可能有多种表示方法，找出最小的X并输出相应的K，你若找到，则政府将奖励那位妈妈，你帮她快速断定一下吧！ 例如 16＝2^4＝4^2,64＝4^3＝2^6=8^2则16应表示为2＾4，64应表示为2＾8。

Input

每行一个正整数N，输入文件以0为结束标志。（0＜N＜10000）

Output

每行有两个整数，如果能表示，则输出X　K，（中间用一个空格隔开）如果不能，则输出0　0；

Sample Input

5
4
16
27
0

Sample Output

0 0

2 2

2 4

3 3
Source
ZJUT1299
这道题用了两种方法来做，都是Wrong Answer，不知为何，还请各位大牛指教！
第一种，若XK = N，则K = logXN = lg(N) / lg(X)，那么通过判断K是否为整数来确定N能否写为N的K次方：
#include<iostream>
#include<cmath>
#include<float.h>
int main(){
    int n;
    while(scanf("%d", &n) != EOF && n){
        int X = 0, K = 0;
        if(n == 1){
            X = 1;
            K = 2;
        }
        else
            for(int i = 2; i <= sqrt((float)n); ++i){
                double tmp = log((float)n) / log((float)i);
                if(fabs(tmp - (int)tmp) <= FLT_EPSILON){	//判断tmp是否为整数
                    K = tmp;
                    X = i;
                    break;
                }
                //printf("%d\n", tmp);
            }
        printf("%d %d\n", X, K);
    }
    return 0;
}
无法通过，因此想到了第二种方法，即用map来存10000以内的所有最小X情况，然后根据用户输入的N直接输出：
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
struct s{
	int X;
	int K;
};
int main(){
	int n = 10000;
	map<int, s> m;
	m[1].X = 1;
	m[1].K = 2;
	for(int i = 2; i <= 100; ++i){
		for(int j = 2; j < 15; ++j){
			int num = pow((float)i, j);
			if(num > 10000 || (m[num].X > 0 && m[num].X < i)){
				break;
			}
			m[num].X = i;
			m[num].K = j;
		}
	}
	while(scanf("%d", &n) != EOF && n){
		printf("%d %d\n", m[n].X, m[n].K);
	}
	return 0;
}
没想到还是Wrong Answer，百思不得其解，还请各位大牛多多指教。。
后记：
让我纠结了这么久的原因竟然是题目出错，AC代码如下：
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
struct s{
    int X;
    int K;
};
int main(){
    int n = 10000;
    map<int, s> m;
    for(int i = 99; i >= 2; --i){
        for(int j = 2; j < 15; ++j){
            int num = pow((float)i, j);
            if(num > 10000 || (m[num].X > 0 && m[num].K < j)){
                continue;
            }
            m[num].X = i;
            m[num].K = j;
        }
    }
    while(scanf("%d", &n) != EOF && n){
        printf("%d %d\n", m[n].X, m[n].K);
    }
    return 0;
}
老师的代码：
#include<iostream>
using namespace std;
struct s{
	int x,y;
} ;
int main(){
	s a[10000];
	for(int k=1;k<=9999;k++)
	{
		a[k].x=0;a[k].y=0;
	}
	for(int i=2; i<100; i++){
		int t=i*i;
		for(int j=2; t<10000; j++,t*=i)
			a[t].x=i, a[t].y=j;
	}
	for(int n; cin>>n && n; )
		cout<<a[n].x<<" "<<a[n].y<<"\n";
}
				
如需转载请注明出处：杰拉斯的博客
				
相关文章
				

					
[ACM_Tyvj_1011]传纸条（双线程动态规划解法）              
					
[ACM_NYOJ_19]擅长排列的小明              
					
[ACM_NYOJ_47]过河问题              
					
[ACM_NYOJ_27]水池数目              
					
[ACM_NYOJ_8]一种排序