poj 1730 Perfect Pth Powers

这个有2种方法。

一种是通过枚举p的值（p的范围是从1-32），这样不会超时，再就是注意下精度用1e-8就可以了，还有要注意负数的处理……

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iomanip>
 6 #include<string>
 7 using namespace std;
 8 int fun(double n)
 9 {
10     int p=32,f=1;
11     if(n<0)
12     {
13         p=31;
14         f=2;
15         n=-n;
16     }
17     for(;p>=1;p-=f)
18     {
19         double a=pow(n,1.0/p);
20         long t1=a;
21         long t2=a+1;
22         if(a-t1<=1e-12||t2-a<=1e-12)
23             break;
24     }
25     return p;
26 }
27 int main()
28 {
29     int x,p;
30     while(cin>>x&&x)
31     {
32         p=fun(x);
33         cout<<p<<endl;
34     }
35     return 0;
36 }

第二种方法就是分解素数因子，求出因子的指数的最大公约数就是答案了，但是我这测试没错，提交超时……

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cmath>
 6 #include<iomanip>
 7 #include<string>
 8 using namespace std;
 9 int prime[100001],a[100001];
10 void init()
11 {
12     int i,j,k=0;
13     for(i=2;i<=100000;i++)
14     {
15         if(!a[i])
16         {
17             prime[k++]=i;
18             for(j=i+i;j<=100000;j+=i)
19                 a[j]=1;
20         }
21     }
22 }
23 int gcd(int a,int b)
24 {
25     int c;
26     if(a<b) swap(a,b);
27     while(b)
28     {
29         c=a;
30         a=b;
31         b=c%b;
32     }
33     return a;
34 }
35 int main()
36 {
37     int n,i,j;
38     bool flag;
39     init();
40     while(scanf("%d",&n),n)
41     {
42         flag=0;
43         if(n<0)
44         {
45             flag=1;
46             n=-n;
47         }
48         vector<int> key;
49         for(i=0;prime[i]*prime[i]<=n;i++)
50         {
51             if(n%prime[i]==0)
52             {
53                 int c=0;
54                 for(;n%prime[i]==0;n/=prime[i],c++);
55                 key.push_back(c);
56             }
57         }
58         if(n>1) key.push_back(1);
59         int sum=key[0];
60         for(i=1;i<key.size();i++)
61             sum=gcd(sum,key[i]);
62         if(flag)
63         {
64             while(sum%2==0)
65                 sum/=2;
66         }
67         printf("%d
",sum);
68     }
69     return 0;
70 }