[整数分解+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 long
using namespace std;
#define MAXN 1000007
bool 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;
}

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

原文：http://blog.csdn.net/wdcjdtc/article/details/44653913