[UVa 10662] Perfect P-th Powers【质因数分解/欧几里得算法/初等数论】

[Description]

给定一个x(int 范围),求它最多能开多少次方。也就是满足x=y^k的最大k值。
[Solution]

把x质因数分解。令x=p1^k1*p2^k2*…*pn^kn,找到所有k的gcd,所以x=(p1^(k1/gcd)*p2^(k2/gcd)*…*pn^(kn/gcd))^gcd.

可以证明,gcd就是最大的指数了。


需要注意的是x<0的情况,此时gcd必须为偶数(不然幂是正数),这时把gcd中所有的2再放进括号就可以了,也就是说,最后得到的gcd是原值不断除2的结果。

x还是开long long比较保险,不然会WA?!

[Code]
#include<cmath>
#include<cstdio>

const int maxn=1<<16;
long long x;

bool form[maxn];
int prime[maxn/10],cnt;
void MakePrimeList(){                  //线性筛质数
    for(int i=2;i<maxn;i++){
if(!form[i]) prime[cnt++]=i;
for(int j=0;prime[j]*i<maxn;j++){
   form[prime[j]*i]=true;
   if(!(i%prime[j])) break;
}
    }
}

int gcd(int x,int y){ return !y?x:gcd(y,x%y); }

int divide(long long x){                 //分解质因数
    int res=0,minu=x<0;
    if(x<0) x=-x;
    for(int i=0;i<cnt && prime[i]<x;i++){
int num=0;
while(!(x%prime[i])) x/=prime[i],num++;
if(num) res=gcd(res,num);
    }
    if(!res || x>1) res=1;
    if(minu) while(!(res%2)) res/=2;
    return res;
}

int main(){
    MakePrimeList();
    while(~scanf("%lld",&x) && x) printf("%d\n",divide(x));
    return 0;
}

此博客中的热门博文

图论专题总结