[整数分解+dfs] light oj 1220 Mysterious Bacteria

题意：

给一个x，问让它被表示成b^p（b的p次方）。p最大是多少。

思路：

将x分解，得到质因子以及个数。

我们知道x是每个质因子幂的乘积，，所以要使得p最大，就是幂最大。

最大其实就是这些质因子个数的最大公约数。

因为超过的就变成乘积放进去。

然后要注意这题输入的x可能是负数。

负数的话要去掉2的约数。

代码：

#include"cstdio"#include"cstring"#include"cmath"#include"cstdlib"#include"algorithm"#include"iostream"#include"map"#include"queue"#define ll long longusing namespace std;#define MAXN 1000007bool mark[MAXN];int ss[MAXN],sscnt;int gcd(int a,int b){return b==0?a:gcd(b,a%b);}void ssb(){sscnt=0;memset(mark,false,sizeof(mark));mark[0]=mark[1]=true;for(int i=2; i<=MAXN; i++){if(!mark[i]){for(int j=i+i; j<=MAXN; j+=i) mark[j]=true;ss[sscnt++]=i;}}return ;}int main(){int t,cas=1;cin>>t;ssb();while(t–){ll n;int f=0;scanf("%lld",&n);if(n<0) f=1,n=-n;int ans=0;for(int i=0; i<sscnt; i++){if((ll)ss[i]*ss[i]>n) break;if(n%ss[i]==0){int tep=0;while(n%ss[i]==0){tep++;n/=ss[i];}if(ans==0) ans=tep;else ans=gcd(ans,tep);}}if(n!=1) ans=1;if(f){while(ans%2==0) ans/=2;}printf("Case %d: %d\n",cas++,ans);}return 0;}

没有行李，没有背包，不带电脑更不要手机，