J - Mysterious Bacteria

本文主要是介绍J - Mysterious Bacteria，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://cn.vjudge.net/contest/70017#problem/J

题目大意：给你一个数a，你要求出最大的一个数x，满足b的x次方等于a；

题解：根据算数基本定理，一个数可以分为a=p1^x1*p2^x2.......*pn^xn;所以算出x1,x2,.....,xn的最大公因子就行了，但是如果a为负数的情况下求出的x一定要为奇数，如果求出的是偶数，那么就要一直把x除以2，知道x为奇数。

代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>using namespace std;const int maxn=1e6+5;
int prime[maxn+1],tag[maxn+1],cnt;void Prime()
{memset(tag,0,sizeof(tag));cnt=0;tag[0]=tag[1]=1;for(int i = 2; i<maxn; i++){if(!tag[i])prime[cnt++]=i;for(int j=0; j<cnt && prime[j]*i<maxn; j++){tag[i*prime[j]] = 1;if(i % prime[j]==0)break;}}
}int ss[maxn];int main()
{Prime();int T;int m=0;scanf("%d",&T);while(T--){long long int a,b;++m;scanf("%lld",&a);b=a;a=abs(a);int ans=0;for(int i=0;i<cnt&&prime[i]*prime[i]<=a;i++){if(a%prime[i]==0){int ii=0;while(a%prime[i]==0){a=a/prime[i];ii++;}if(ii!=0)ss[++ans]=ii;}}if(a>1){printf("Case %d: 1\n",m);}else{int num=ss[1];for(int i=2;i<=ans;i++){num=__gcd(num,ss[i]%num);}if(b<0){while(num%2!=1){num=num/2;}}printf("Case %d: %d\n",m,num);}}return 0;
}

 

这篇关于J - Mysterious Bacteria的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---