POJ 1730 Perfect Pth Powers 素数分解

发表于 | 分类于 | 阅读次数:
字数统计: 356 字

题目链接： 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);
	}
}