Poj 1730 Perfect Pth Powers (数论 GCD)

本是古典何须时尚 2022-09-19 10:59 18阅读 0赞

期末考正式结束，虽然还有实习、课设等各种坑爹事情，但应该能静下心来学习点新东西了。

前段时间做的题，思路比较好想，但我果断被细节坑了。。。。

题意：给出整数x，求使得等式x=b^p成立的最大的p。

思路：对x进行素数分解，则所有素因子的指数的最大公约数即为所求。给出的x可以是负数……负数的情况要先把x变成-x去计算，显然只有奇数次乘方才有可能是负数(我们不考虑复数……)，所以如果最后结果是偶数，要不断将结果减半，直到为奇数。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int N=100005;
    int prime[N],indexmax[N];
    int np=0,n;
    bool visit[N];
    bool flag;
    
    void Prime ()   //素数打表prime数组从0开始
    {
        for (int i=2;i<N;i++)
    		if (!visit[i])
    		{
    			prime[np++]=i;
    			for (int j=i+i;j<N;j+=i)
    				visit[j]=true;
    		}
    }
    
    int Gcd (int x,int y)  
    {  
        return !y?x:Gcd(y,x%y);  
    }
    
    void Deal ()
    {
    	int id=0,i;
    	memset(indexmax,0,sizeof(indexmax));
    	__int64 temp=n;
    	for (i=0;(__int64)prime[i]*prime[i] <= temp; i++)
    	{
    		int t=0;
    		while (temp%prime[i] == 0)
    		{
    			t++;
    			temp/=prime[i];
    		}
    		if (t!=0)
    			indexmax[id++]=t;//记录素因子p[i]的个数
    	}
    	if (temp>1)   //未除尽
    		indexmax[id++]=1;
    	int ans=indexmax[0];
    	if (id>1)
    		for (i=1;i<id;i++)
    			ans=Gcd(ans,indexmax[i]);
    	if (flag)
    		while (ans%2==0)
    			ans/=2;
    	printf("%d\n",ans);
    }
    
    int main ()
    {
    	Prime ();
    	while (scanf("%d",&n),n)
    	{
    		flag=false;
    		if (n==-2147483648)
    		{
    			printf("31\n");
    			continue;
    		}
    		if (n<0)
    		{
    			n=-n;
    			flag=true;
    		}
    		if (n==1)
    		{
    			printf("1\n");
    			continue;
    		}
    		Deal ();
    	}
    	return 0;
    }