POJ 1730 Perfect Pth Powers 素数分解

题目链接: http://poj.org/problem?id=1730

题意

如果一个数x能够被表示成b^p这样的形式,称x为完美p次方数,现在给出x求最大的p使得其为一个完美p次方树

题解

利用素数分解,如果x为正数的话,最大的p就是这个数的素因子幂级数的最大公因数。
如果x为奇数的话,先转化为正数进行计算,最后将结果不断除2直到变成奇数。因为偶次方是不可能得到一个正数的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
t ll maxp=100003;
bool is_prime[maxp];
int prime[maxp],num;

void prime_init()
{
num=0;
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
for(int i=2;i<maxp;i++)
{
if(is_prime[i]) prime[num++]=i;
for(int j=0;j<num && i*prime[j]<maxp;j++)
{
is_prime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
}

int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}

void solve()
{
ll x;
prime_init();
while(scanf("%lld",&x)!=EOF && x)
{
ll ans=-1,i=0,tmp;
bool flag=0;
if(x<0)
x=-x,flag=1;
while(x!=1 && i<num-1)
{
tmp=0;
while(x%prime[i]==0)
{
tmp++;
x/=prime[i];
}
i++;
ans=ans==-1?tmp:gcd(ans,tmp);
}
if(x!=1) ans=1;
if(flag) //如果是负数的话将ans变为奇数
while(ans%2==0)
ans/=2;
printf("%lld\n",ans);
}
}